백준 1446번: 지름길 [Python]

작성일 | In
실버 I 실버 I

문제

지름길

생각보다 까다로운 DP 문제였습니다.

풀이

문제의 답을 $DP[D]$라 합시다. 끝 위치가 $e$인 모든 지름길의 시작 위치를 $s_i$, 길이를 $d_i$라 합시다.

그렇다면 $DP[e] = \min(DP[e - 1], DP[s_i] + d_i)$의 점화식으로 답을 구할 수 있습니다.

저는 지름길을 효율적으로 보기 위해서 내림차순 정렬 후 스택에 넣어서 필요한 것만 $O(1)$에 꺼냈지만, $N$이 충분히 작으므로 어떻게 구현하든 크게 상관 없습니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
INF = int(1e9)


def main():
    N, D = map(int, input().split())

    shortcuts = [list(map(int, input().split())) for _ in range(N)]
    shortcuts.sort(reverse=True)

    minDist = [INF] * (10001)
    minDist[0] = 0

    for i in range(0, D + 1):
        minDist[i] = min(minDist[i], minDist[i - 1] + 1)

        while shortcuts:
            s, e, d = shortcuts[-1]
            if s < i:
                shortcuts.pop()
            if s != i:
                break

            minDist[e] = min(minDist[e], minDist[s] + d)
            shortcuts.pop()

    print(minDist[D])


main()

백준 1446번: 지름길 [Python]