[BOJ] 16210 - DSHS Bank

1. 문제 정리

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

링크를 확인해보세요.

www.acmicpc.net

• N개의 2차원 좌표를 줍니다.
• 다름 모든 좌표와의 맨해튼 거리의 합이 가장 적은 좌표를 구하면 됩니다.
• 합이 가장 적은 좌표가 여러 개인 경우 먼저 주어진 좌표의 순번을 출력합니다.
  • 좌표의 번호는 1부터 시작됩니다.

2. 문제 풀이

아이디어

• 서브 태스크 2에서 힌트를 얻었습니다.
• [A, B, C, D, E, F] 정렬된 좌표가 주어졌다고 가정하고, 한 축의 좌표값이 0으로 고정했다고 하면
• C의 맨해튼 거리의 합은 다음과 같습니다.
• |A - C| + |B - C| + |D - C| + |E - C| + |F - C|
• 이를 정렬 되어있으므로 절댓값 부호를 없애면 다음과 같습니다.
  • 2 * C - (A + B) + (D + E + F) - 3 * C
  • 2는 C 기준 앞에 있는 좌표 개수, 3은 C 기준 뒤에 있는 좌표 개수
• 이걸 통하여 누적합만 계산되면 O(N)으로 N개의 좌표에 대하여 맨해튼 거리를 구할 수 있게 됩니다.

결론

• 각 좌표의 x축과 y축 좌표를 분리하여 O(N)으로 맨해튼 거리를 구합니다.
• x축과 y축의 합을 더하여 최종해를 찾습니다.

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    void calcDistance(int[] loc, Integer[] offset, long[] distance, long rightSum) {
        int N = distance.length;

        long leftSum = 0;
        for (int off = 0; off < N; off++) {
            int idx = offset[off];   // 실제 좌표의 위치 (주어진 좌표의 순번)
            long idxLoc = loc[idx];  // 실제 좌표 값.

            rightSum -= idxLoc;

            // 현재 좌표 기준 좌/우에 있는 첨들의 맨해튼 거리.
            long left = idxLoc * off - leftSum;
            long right = rightSum - idxLoc * (N - 1 - off);

            distance[idx] += (left + right);

            leftSum += idxLoc;
        }
    }

    void solve() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //== 입력 받기 및 초기화
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[] xLoc = new int[N];    // x 좌표 모음
        int[] yLoc = new int[N];    // y 좌표 모음

        long xSum = 0, ySum = 0;

        // 각 x축, y축 좌표의 offset 저장. 정렬 후에도 index를 기억하기 위함.
        Integer[] xOffset = new Integer[N];
        Integer[] yOffset = new Integer[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            xLoc[i] = x;
            yLoc[i] = y;

            xSum += x;
            ySum += y;

            xOffset[i] = i;
            yOffset[i] = i;
        }

        // 각 축 좌표를 오름차순으로 정렬.
        Arrays.sort(xOffset, Comparator.comparingInt(i -> xLoc[i]));
        Arrays.sort(yOffset, Comparator.comparingInt(i -> yLoc[i]));

        //== 로직 처리.

        // 각 축 좌표간의 거리 구하기.
        long[] distance = new long[N];

        calcDistance(xLoc, xOffset, distance, xSum);
        calcDistance(yLoc, yOffset, distance, ySum);

        // 가장 짧은 거리 구하기.
        int minIdx = N;
        long minDistance = Long.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            if (distance[i] < minDistance) {
                minIdx = i;
                minDistance = distance[i];
            }
        }

        System.out.println(minIdx + 1);
    }

    public static void main(String[] args) throws Exception {
        new Main().solve();
    }
}

추가

• 서브 태스크가 있는 문제인 경우, 제출 화면에서 언어를 클릭하면 각 테스크에 대한 정보를 알 수 있습니다.

틀린 줄도 모르고 시간복잡도 문제라고 생각해서 1시간 내내 최적화만 고민했습니다. ㅎㅎ