[파이썬] 백준 10217 : KCM Travel (플레5)

[파이썬] 백준 10217 : KCM Travel (플레5)

10217번: KCM Travel

---

문제

---

풀이

방향성 생각

• 다익스트라 + 2차원 visit (노드, 사용금액) = 시간기록
• node가 100 / 지원비용 10000 = 100만이라서 메모리가 좀 빡빡해보인다 -> 당연하게도(?) 터져버림
• 최대로 지원금이 m으로 정해짐 -> 냅색? (사실 DP 태그보고 알았음 ㅋㅋ)

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

inf = float('inf')
input()
n,m,k = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(k):
    a,b,cost,time = map(int,input().split())
    graph[a].append((b,cost,time)) 

dp = [[inf for _ in range(n+1)] for _ in range(m+1)]
dp[0][1] = 0

for s in range(m+1):
    for x in range(1,n+1):
        if dp[s][x] != inf:
            for nx,cost,time in graph[x]:
                if s+cost <= m:
                    dp[s+cost][nx] = min(dp[s+cost][nx],dp[s][x]+time)

answer = min(dp[i][n] for i in range(m+1))
print(answer if answer != inf else 'Poor KCM')

 

코멘트

냅색을 떠올리기가 쉽지 않았습니다....

당연히 다익으로 푸는게 정해라고 생각해서 구현했는데, 다차원 배열을 만드는 순간 터질거같다고 생각했다.

제출했는데 당연히 터져버려서 힙을 큐로, 쓸데없는 메모리를 줄이려고 visit을 defaultdict로 바꾸는 등 최적화를 해봤는데 이런거 다 먹어버리는 테케가 있어서 실패.