문제(Platinum4)
N개의 체커가 엄청 큰 보드 위에 있다. i번 체커는 (xi, yi)에 있다. 같은 칸에 여러 체커가 있을 수도 있다. 체커를 한 번 움직이는 것은 그 체커를 위, 왼쪽, 오른쪽, 아래 중의 한 방향으로 한 칸 움직이는 것이다.
입력
첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 체커의 x좌표와 y좌표가 주어진다. 이 값은 1,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 수 N개를 출력한다. k번째 수는 적어도 k개의 체커가 같은 칸에 모이도록 체커를 이동해야 하는 최소 횟수이다.
예제 입력 1
4
15 14
15 16
14 15
16 15
예제 출력 1
0 2 3 4
예제 입력 2
4
1 1
2 1
4 1
9 1
예제 출력 2
0 1 3 10
풀이 과정
1번 아이디어: x의 거리, y의 거리를 구분해서 계산 해 준 뒤 합쳐서 최소값을 구해주면 된다.
2번 아이디어: 한 곳에서 모일 때, 비용을 최소화 하기 위해서는 점들 중 한 곳에서 모이면 된다.
3번 아이디어: n점이 모였을 때의 최소거리를 구하고 싶다면 해당 점에서 가까운 n점의 거리만 더해주면 된다.
처음에는 (14,14)~(15,15) 총 9개의 좌표를 확인 했었다.
하지만 해당 방법으로 문제를 풀었을 때는 각 x값과 y값의 min/max값을 구하여 따로 저장 후 계산하다보니 메모리 초과 실패가 계속 되었다.
그러다 다른 분들의 코드를 참고하여 풀게 되었는데, 총 9개의 좌표를 확인하는 것이 아닌 n*n개의 좌표를 확인해야 하는 것이었다.
해당 입력 좌표를 보면, 내가 처음에 짰었던 코드는 (12, 12)~(16,16)까지 총 25개의 좌표를 비교해야한다.
하지만 [x] ×[y]의 값을 비교해버리면 총 n×n인 16개의 좌표만 비교하면 되는 것이다.
min값과 max 값을 구할 필요가 없는 것이었다.
처음에는 다른 분들의 코드를 참고했을 때 왜 n×n의 값을 사용하는지 이해하지 못해 다른 사람들 코드와 비슷하게 짤 수 밖에 없었다.(물론 다른 분들의 코드가 내가 고민했던 방식보다 효율적이긴 하다.)
하지만 이러한 이유로 n×n을 사용해야하는 것을 깨닫고, 내가 처음에 풀어봤던 코드를 살짝만 수정하여 정답을 낼 수 있었다.
해당 문제를 풀면서 처음에는 최대한 한 개의 for문 내에서 비용을 sort 후 계산하고 싶었는데, 혼자서 답을 내지 못했던 게 아쉽다.
깃허브 코드 주소는 여기
그리고 ... 깃허브에 남겨진 고민의 기록들
인프런에서 알고리즘 강의를 들으며 과제로 내 주신 문제여서 강사님의 힌트를 듣고 풀게 되었다.
나도 언젠가 강사님처럼 생각하고 싶다. 그때까지 파이팅.
