[Python] 백준 - 2828 사과 담기 게임

출처: 백준 온라인 저지
https://www.acmicpc.net/problem/2828

그림은 르네 마그리트의 <청취실>(1952)

처음 풀이 (틀린 풀이)

from sys import stdin


n, m = map(int, stdin.readline().split())
j = int(stdin.readline())

p_list = []
distance = 0

for _ in range(j):
    p = int(stdin.readline())
    p_list.append(p)

    if (value := max(p_list) - min(p_list) - m) >= 0:
        distance += (value + 1)

        if p == max(p_list):
            p_list = [p - m + 1, p]
        else:
            p_list = [p + m - 1, p]

print(distance)

사과가 떨어지는 위치에 맞게 그때 그때 최소한으로 바구니를 움직여서, 바구니의 총 움직인 거리를 최소화하는 어렵지 않은 그리디 알고리즘 문제였다. 다만 처음 바구니의 위치를 지정하는 문제가 까다로웠다. 그래도 시행착오를 거쳐 겨우 코드를 완성했는데, 정답 인정이 되지 않았다. 알고 보니 문제에서 바구니의 시작 위치를 지정해주었다. 괜히 더 어렵게 푼 것이다.

최종 풀이

from sys import stdin


n, m = map(int, stdin.readline().split())
j = int(stdin.readline())

start = 1
end = m
distance = 0

for _ in range(j):
    p = int(stdin.readline())

    if p < start:
        distance += (start - p)
        start = p
        end = p + m - 1

    elif p > end:
        distance += (p - end)
        end = p
        start = end - m + 1

print(distance)

결론 : 문제에서 주어진 조건을 놓치지 않도록 문제를 꼼꼼히 읽도록 하자.