(백준) 인문예술탐사주간 _ 23829

https://www.acmicpc.net/problem/23829

 

🐢 설명

이분탐색과 누적합을 이용해서 풀 수 있는 문제였다. 간단하지만 lower_bound로 구한 위치에서의 나무가 자신의 위치와의 차이 별로 따로 처리해야 하는 부분이 좀 어려웠었다.

 

주어진 나무들이 있고 자신의 위치가 주어진다. 이때 자신의 위치와 나무의 위치를 비교해서 모든 거리의 합을 각 위치별로 출력하면 되는 문제이다. 이때 모든 나무들을 먼저 정렬하고, 누적합을 만들어 준다.

정렬된 나무들에 대해서 자신보다 크거나 같은 최초의 나무 위치를 구하기 위해 lowerBound()를 이용해 구한다. 이 작업은 logN 이므로 10만개의 나무에 대해 빠른 비교를 할 수 있다.

 

이렇게 구한 위치의 나무가 자신의 위치와 차이가 어떻냐에 따라 구분해야줘야 한다.

1. mid번째 나무의 위치가 자신의 위치보다 작거나 같은 경우
2. mid번째 나무의 위치가 자신의 위치보다큰 경우

즉 자신의 위치보다 가깝거나 같은지 아니면 먼지에 따라 왼쪽의 계산식 or 오른쪽 계산식에 포함해서 계산해줘야 한다.

 

자신의 위치보다 mid 번째 나무가 작거나 같다면 해당 위치를 기준으로 (mid * 자신의 위치) - mid번 나무 누적합을 구해주고, 오른쪽은
((N번 나무 누적합 - mid번 나무 누적합) - (N -mid) * 자신의 위치))을 구해 주면된다.

 

자신의 위치보다 mid번째 나무가 크다면 왼쪽을 구할 때 mid번째 나무를 제외하고 구해줘야하고, 오른쪽에서 왼쪽의 누적합을 뺄 때에도 mid나무 이전 나무들의 누적합만 빼줘야 한다. 오른쪽 나무의 개수 또한 (N - mid + 1)개 로 해당 나무를 포함 시켜줘야 한다.

 

 

🐢코드

public class 인문예술탐사주간_23829 {
    static int N, Q;
    static int[] treePos;
    static long[] cumulativeSum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder answer = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
        treePos = new int[N + 1];
        cumulativeSum = new long[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            treePos[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(treePos);
        for (int i = 1; i <= N; i++) {
            if (i == 1) cumulativeSum[i] = treePos[i];
            else cumulativeSum[i] = cumulativeSum[i - 1] + treePos[i];
        }

        for (int i = 0; i < Q; i++) {
            long dist = Integer.parseInt(br.readLine());
            int mid = lowerBound(dist);

            long leftSum;
            long rightSum;

            if (treePos[mid] <= dist) { // 현재 나무가 작거나 같은 경우, 현재 나무를 왼쪽 나무로 포함시킨다.
                leftSum = (mid * dist) - cumulativeSum[mid];
                rightSum = (cumulativeSum[N] - cumulativeSum[mid]) - ((long) (N - mid) * dist);
            } else { // 현재 나무가 큰 경우, 현재 나무를 오른쪽 나무로 포함시킨다.
                leftSum = ((mid - 1) * dist) - cumulativeSum[mid - 1];
                rightSum = (cumulativeSum[N] - cumulativeSum[mid - 1]) - ((long) (N - mid + 1) * dist);
            }

            answer.append((leftSum + rightSum)).append("\n");
        }
        System.out.print(answer);
    }

    private static int lowerBound(long pos) {
        int left = 1;
        int right = N;
        int mid = 0;

        while (left <= right) {
            mid = (left + right) / 2;

            if (treePos[mid] > pos)
                right = mid - 1;
            else if (treePos[mid] < pos)
                left = mid + 1;
            else
                break;
        }
        return mid;
    }
}

 

🐢 마무리