백준 2157 여행

유형 : dp

 

문제풀이

* 지금 설명할 풀이는 효율이 좋지 못합니다.

 b 도시에 i번째로 도착했을 때, 가능한 기내식 점수들의 합은 dp[a][i-1]+air[a][b] 가 됩니다. (air[a][b]는 a에서 b 구간 비행기의 기내식의 점수)

 따라서 dp[b][i]의 점화식은 아래와 같이 쓸 수 있습니다.

 dp[b][i] = max(dp[a][i-1]+air[a][b] for b보다 작은 모든 a)

 다만 위의 식을 진행하는 데에 있어서, i-1번째로 a에 도착한 경우와 a에서 b구간의 비행기가 있다는 조건을 위한 조건문이 추가로 들어가야합니다.

 위의 점화식을 b를 n까지, i는 m까지 반복 한 후, dp[n]의 최댓값을 반환하면 됩니다.

 

Python Code

import sys
n,m,k = map(int,sys.stdin.readline().split())
air = [[0 for i in range(n+1)] for j in range(n+1)]
#dp[도시][몇번째]
dp = [[0 for i in range(k+1)] for j in range(n+1)]
for _ in range(k):
    a,b,c = map(int,sys.stdin.readline().split())
    air[a][b] = max(air[a][b],c)
for b in range(2, n+1):
    dp[b][2] = air[1][b]
for b in range(2,n+1):
    for i in range(3,m+1):
        try:
            dp[b][i] = max(dp[a][i-1]+air[a][b] for a in range(1,b) if air[a][b] and dp[a][i-1])
        except:
            pass
print(max(dp[n]))

line13에 try 문이 들어간 이유는 if문을 만족하는 a가 하나도 없는 경우 max함수에서 에러가 발생하기 때문입니다.

 

문제링크

2157번: 여행