[Week of Line Sweep] BOJ 7571

어제에 이어 오늘도 Line Sweep 문제를 풀었다.

Line Sweep 문제는 거의 2D의 격자나 1D의 Line 형태로 된 문제인거 같은데

이번 문제는 2D 격자로 구성된 문제였다.

 

문제를 딱 본 순간 각 좌표들의 평균값에 해당하는 좌표를 구해서

각 좌표에서 빼준 값을 누적하면 될거 같아서 그렇게 풀었다.

 

그런데 WA(Wrong Answer)..

뭐가 문제지 하고 반례를 찾아봤더니

(1,1), (1,2), (1,6) 인 경우

평균 좌표는 (1,3) 이며 

각 좌표에서 거리를 누적한 값은 6이 된다.

그러나 (1,2)를 기준으로 거리를 누적한 값은 5가 된다.

 

풀이도 같이 찾아봤는데

상기의 예에서 (1,2)는 '중간값'이라고 표현했다.

 

결국 각 좌표에 대한 평균값 좌표가 아닌 중간값 좌표를 구해서

거리를 누적하여 답을 내면 되는 것이었다.

 

작성한 소스는 아래와 같다.

from sys import stdin

if __name__ == "__main__":
    n, m = map(int, stdin.readline().split(' '))
    x = [0 for _ in range(m)]
    y = [0 for _ in range(m)]
    mx, my = 0, 0
    res = 0
    for i in range(m):
        x[i], y[i] = map(int, stdin.readline().split(' '))
    x.sort()
    y.sort()

    mx = x[m // 2]
    my = y[m // 2]
    for i in range(m):
        res += abs(x[i]-mx) + abs(y[i]-my)

    print(res)

그리 어려운 난이도는 아니었지만

평균값으로만 풀어야 한다는 고정관념을 버리지 않는다면

시간만 질질 끌다가 다른 문제를 풀지 못하는 상황이 발생했을 수도 있을것 같다.