[BOJ] 7571 - 점 모으기 (Python)

 

 

아이디어 #1

 

이동거리 합이 최소가 되는 위치는 행과 열 번호 각각의 중앙값이므로, 각 번호와 중앙값과의 차를 모두 더한다.

 

 

풀이 #1

 

행과 열을 구분하여 입력 받은 번호들을 정렬한 후 각각의 중앙값을 찾아 계산한다.

 

import sys

input = sys.stdin.readline

def solution():
    N, M = map(int, input().split())
    R, C = [], []
    for _ in range(M):
        r, c = map(int, input().split())
        R.append(r)
        C.append(c)
    R.sort()
    C.sort()
    res = 0
    mr = R[M//2]
    mc = C[M//2]
    if M%2 == 0:
        mr = (mr+R[M//2-1])//2
        mc = (mc+C[M//2-1])//2
    for i in range(M//2):
        res += mr-R[i]+mc-C[i]
    for i in range(M//2, M):
        res += R[i]-mr+C[i]-mc
    print(res)

solution()

 

 

 

아이디어 #2

 

계수 정렬을 이용해 이동거리 합의 최솟값을 구한다.

 

 

풀이 #2

 

행과 열을 구분해 번호별 개수와 번호 합을 구한다.

번호 합에 지난 점의 개수만큼씩 더하고, 지나지 않은 점의 개수만큼씩 빼면서 최솟값을 구한다.

 

import sys

input = sys.stdin.readline

def solution():
    N, M = map(int, input().split())
    cnt_list_R = [0]*(N+1)
    cnt_list_C = [0]*(N+1)
    sum_R = sum_C = 0
    for _ in range(M):
        r, c = map(int, input().split())
        cnt_list_R[r] += 1
        cnt_list_C[c] += 1
        sum_R += r
        sum_C += c
    cnt_R = cnt_C = 0
    min_R, min_C = sum_R, sum_C
    for i in range(1, N+1):
        sum_R += cnt_R-(M-cnt_R)
        cnt_R += cnt_list_R[i]
        if sum_R < min_R:
            min_R = sum_R
        sum_C += cnt_C-(M-cnt_C)
        cnt_C += cnt_list_C[i]
        if sum_C < min_C:
            min_C = sum_C
    print(min_R+min_C)

solution()