[python] 백준 2157 여행

https://www.acmicpc.net/problem/2157

2157번: 여행

 

문제 해결

• 처음에 다익스트라로 풀려고 했으나 k가 매우 클 수 있는 바람에 시간초과가 났다.
• 큰 수를 계산해야할 때는 무조건 dp가 된다!
• 그럼 dp를 어떻게 잡아야할까?
• 우선 똑같은 출발지에서 도착지점까지 항공로가 여러가지가 있을 수 있기 때문에 graph를 $ n \times n$ 행렬을 만든다음 graph[i][j]의 값읠 i에서 j까지 가는 항공로 중 최대 점수라고 정의하고 값을 넣는다.
• dp[i][j]는 1에서 i까지 누적해서 j개의 도시를 가면서 얻은 점수라고 정의를 한다.
• 그러면 dp[i][j] = max(dp[i][j], dp[l][j-1]+graph[l][i]) 가 된다. (참고로 l<i 이며 j<m+1 이다.)
• 이렇게 생각하면 코드 구현하긴 쉽다!

 

CODE

import sys
input = sys.stdin.readline
n, m, k = map(int,input().split())
graph = [[0]*(n+1) for _ in range(n+1)] # graph[i][j] i에서 j까지 가는데 value 최댓값
dp =[[0]*(m+1) for _ in range(n+1)] # dp[i][j]는 1번에서 i까지 j개의 도시를 걸쳐(1,j 포함) 갈 수 있는 최댓값
for _ in range(k):
    start, end, value = map(int, input().split())
    if start>end: continue
    graph[start][end] = max(graph[start][end],value)
for i in range(2,n+1):
    dp[i][2] = graph[1][i]
for i in range(2,n+1):
    for j in range(3,m+1):
        for l in range(1,i):
            if graph[l][i] and dp[l][j-1]:
                dp[i][j] = max(dp[i][j],dp[l][j-1]+graph[l][i])
print(max(dp[n]))