[Python/파이썬] 백준 2157번 여행

2157번: 여행

 

코드

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
path = [[-1]*(n+1) for _ in range(n+1)]  # path[i][j] : i->j로 갈 때 기내식 점수
for _ in range(k):
    a, b, c = map(int, input().split())
    if a < b:   # 동->서로 가는 경우에만 기내식 점수 저장
        path[a][b] = max(path[a][b], c)

# dp[i][j] : i번 도시까지 j개의 도시를 지나며 먹는 기내식 점수 총 합의 최대값
dp = [[-1]*(m+1) for _ in range(n+1)]
dp[1][1] = 0
for i in range(2, n+1):
    for j in range(2, m+1):
        for k in range(1, i):   # 나보다 동쪽에 있는 도시들 모두 탐색
            if dp[k][j-1] >= 0 and path[k][i] > 0:
                dp[i][j] = max(dp[i][j], dp[k][j-1]+path[k][i])
ans = 0
for i in range(1, m+1):
    ans = max(ans, dp[n][i])
print(ans)

 

처음에 BFS로 풀이했더니 메모리 초과가 발생했다. 메모리 제한은 128mb인데 BFS를 진행하며 큐에 들어가는 원소들이 너무 많아서 그랬던것 같다. 그래서 DP로 다시 풀이했다.

 

dp[i][j] : i번 도시까지 j개의 도시를 지나며 먹는 기내식 점수의 총 합의 최대값을 저장한다. 그러므로 dp[i][j]의 값을 구할 때는 나보다 동쪽에 있는 도시, 즉 번호가 작은 모든 도시(for k in range(1, i))들에 j-1개의 도시를 거쳐서 도달할 때의 값인 dp[k][j-1]에 k번 도시에서 i번 도시로 올 때 먹는 기내식 점수인 path[k][i]를 더한 값(dp[k][j-1]+path[k][i])과 기존의 dp[i][j]을 비교하여 더 큰 값을 저장하면 된다.

 

이렇게 모두 구한 뒤 n에 도달했을 때 m개 이하의 도시를 지나며 얻을 수 있는 기내식의 점수의 총 합의 최대값을 구하면 된다. dp[n][1:m+1]에 저장된 값 중 최대값이 그 답이다.