[백준, Java] 23829번,인물예술탐사주간(누적합)

문제 링크

23829번: 인문예술탐사주간

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. N 그루의 나무는 각 특정 위치에 존재하고 있습니다.

2. 특정 위치에서 나무 사진을 찍을 때 점수는 나무까지 거리의 합입니다.

3. Q개의 위치가 주어질 때 각 사진의 점수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 누적합을 이용하여 1 ~ 최대 위치 기준 거리를 탐색합니다.

 

3. 탐색으로 얻은 각 위치에 대한 사진의 점수를 결과로 출력합니다.

 

사진 점수 구하기(누적합)

 

주어진 사진 찍는 위치에서 매 번 나무의 거리를 구할 수 있지만, 나무의 개수와 주어지는 위치의 개수가 크기 때문에 시간초과가 발생합니다.

 

▶︎ 그래서 반복적인 거리 구하는 과정을 최소화하기 위해서 누적합을 이용할 것입니다.

 

1. 위치에 따른 나무의 거리 변화량

 

 

만약 사진찍는 위치를 빨간색 ▶︎ 하늘색으로 이동할 때에 나무까지의 거리 변화량을 살펴보면 아래와 같습니다.

즉, 이동하는 방향과 거리에 따라 특정 위치에서 나무의 거리가 변화됩니다.

 

위치가 1일 때 각 나무의 거리를 구한 뒤 +1씩 거리를 이동하면서 각 나무의 변화량에 맞게 변경시켜주시면 됩니다.

 

+1씩 지나가는 것으로 왼쪽의 나무의 수만큼 거리가 증가하고 오른쪽에 있는 나무의 수만큼 거리가 감소하게 됩니다.

 

예를 들어,

 

현재 위치 : x

 

왼쪽 나무의 수 : 3 그루

 

오른쪽 나무의 수 : 5그루

 

(x+1)칸으로 이동하였을 때 나무의 거리 : x칸 나무의 거리 + 3(왼쪽) - 5(오른쪽)

 

위와 같이 문제 1 ~ 주어진 특정 최대 위치까지 나무의 거리를 계산을 진행합니다.

 

계산한 위치를 기준으로 특정 위치들의 나무 거리를 결과로 출력하게 됩니다.

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N	Q
5	2

 

 

사진 찍는 위치

4

12

 

 

2. 누적합을 이용하여 1 ~ 최대 위치 기준 거리를 탐색합니다.

 

1번 위치일 때 나무의 거리

 

 

0 + 2 + 6 + 8 + 9 = 25

 

다음(2)으로 이동할 때 왼쪽, 오른쪽 나무의 개수

 

 

왼쪽에 있는 나무 : 1개

 

오른쪽에 있는 나무 : 4개

 

2번 위치일 때 나무의 거리

 

 

위치 2일 때 나무의 거리 : 1칸 나무의 거리(25) + 1(왼쪽) - 4(오른쪽) = 22

 

다음(3)으로 이동할 때 왼쪽, 오른쪽 나무의 개수

 

왼쪽에 있는 나무 : 1개

 

오른쪽에 있는 나무 : 4개

 

3번 위치일 때 나무의 거리

 

위치 3일 때 나무의 거리 : 2칸 나무의 거리(22) + 1(왼쪽) - 4(오른쪽) = 19

 

다음(4)으로 이동할 때 왼쪽, 오른쪽 나무의 개수

 

왼쪽에 있는 나무 : 2개

 

오른쪽에 있는 나무 : 3개

 

 

 

....

 

 

 

12번 위치일 때 나무의 거리

 

 

위치 12일 때 나무의 거리 : 11칸 나무의 거리(25) + 5(왼쪽) - 0(오른쪽) = 30

 

 

 

 

3. 탐색으로 얻은 각 위치에 대한 나무의 거리를 결과로 출력합니다.

 

1	2	3	4	5	6	7	8	9	10	11	12
25	22	19	18	17	16	15	16	17	20	25	30

 

특정 위치1(4) = 18

 

특정 위치1(12) = 30

 

18 30 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해서 나무 및 위치 정보 띄어쓰기 기준 나누었습니다.
• 위치 1을 기준으로 나무의 거리를 구한 뒤 왼쪽, 오른쪽 나무 개수를 세팅합니다.
• 1 ~ 최대 특정 위치까지 +1칸씩 이동하며 사진의 점수를 구합니다.
• 탐색을 통해 Q개 위치의 사진 점수를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws Exception {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine()," ");
        int[] pos = new int[n];
        //위치가 1일 때 각 나무까지 거리의 합
        long basicDistance = 0L;
        //나무 정보 저장 및 정렬
        for(int i=0;i<n;i++){
            pos[i] = Integer.parseInt(st.nextToken());
            //위치가 1일 때 각 나무까지 거리 구하기
            basicDistance += pos[i] -1;
        }
        Arrays.sort(pos);
        int[] targets = new int[m];
        int maxPos = 0;
        //목표 위치 저장 및 최대 위치 구하기
        for(int i=0;i<m;i++){
            targets[i] = Integer.parseInt(br.readLine());
            maxPos = Math.max(maxPos, targets[i]);
        }
        //1 ~ 최대 위치 기준 나무 거리의 합 저장할 배열 설정
        long[] distance = new long[maxPos+1];
        distance[1] = basicDistance;
        //위치 1 기준 왼쪽, 오른쪽 나무 개수 설정
        int left = 0;
        int right = n;
        int idx = 0;
        while(idx < n && pos[idx] == 1 ){
            left++;
            right--;
            idx++;
        }
        //각 위치에서 왼쪽, 오른쪽 나무 개수를 이용해 거리 구하기
        for(int i=2;i<=maxPos;i++){
            distance[i]= distance[i-1] + left - right;
            while(idx < n && pos[idx] == i){
                left++;
                right--;
                idx++;
            }
        }
        
        //목표 위치에 대한 결과값 BufferedWriter 저장
        for(int target : targets){
            bw.write(String.valueOf(distance[target]));
            bw.newLine();
        }
        bw.flush();     //결과 출력
        bw.close();
        br.close();
    }
}