[PS] 1090 체커

🍒 문제

N개의 체커가 엄청 큰 보드 위에 있다. i번 체커는 (xi, yi)에 있다. 같은 칸에 여러 체커가 있을 수도 있다. 체커를 한 번 움직이는 것은 그 체커를 위, 왼쪽, 오른쪽, 아래 중의 한 방향으로 한 칸 움직이는 것이다. 입력 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 체커의 x좌표와 y좌표가 주어진다. 이 값은 1,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 수 N개를 출력한다. k번째 수는 적어도 k개의 체커가 같은 칸에 모이도록 체커를 이동해야 하는 최소 횟수이다.

✅ 내 답

• answer 선언 시 주어진 조건에서 가장 큰 거리의 값으로 초기화
• 주어진 좌표값(x, y) 중 한 점까지의 거리를 계산하여 sorting
• 작은 값부터 더해가며 answer와 크기 비교

import sys

num = int(input())
answer = [int(1e9)]*num

points = [list(map(int,sys.stdin.readline().strip().split())) for _ in range(num)]


x_set = set(x for x, y in points)
y_set = set(y for x, y in points)

for x in x_set:
    for y in y_set:
        dist_arr = []
        for src_point in points:
            dist = abs(x - src_point[0]) + abs(y - src_point[1])
            dist_arr.append(dist)
        dist_arr = sorted(dist_arr)
        
        for k in range(num):
            if sum(dist_arr[:k+1]) < answer[k]:
                answer[k] = sum(dist_arr[:k+1])

print(' '.join(map(str, answer)))

 

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

와 첫 플래티넘.. 감개무량입니다