[ BOJ ] 2157 : 여행 ( GOLD 4 ) / Python

문제 링크 : https://www.acmicpc.net/problem/2157

2157번: 여행

 

문제

N개의 도시가 동쪽에서 서쪽으로 순서대로 위치해 있다. 제일 동쪽에 있는 도시는 1번 도시이며, 제일 서쪽에 있는 도시는 N번 도시이다.

당신은 이와 같은 도시 중에서 M개 이하의 도시를 지나는 여행을 계획하려 한다. 여행 경로는 반드시 1번 도시에서 시작해서 N번 도시에서 끝나야 한다. 물론 이 두 도시도 M개의 도시에 포함된다. 당신은 시차에 매우 민감하기 때문에, 한 번 서쪽으로 이동했다가 다시 동쪽으로 이동하면 몸이 대단히 아프다. 그래서 당신은 계속 서쪽으로만, 즉 도시 번호가 증가하는 순서대로만 이동하기로 하였다.

한편, 모든 도시에서 다른 모든 도시로 이동할 수 있는 건 아니다. 각각의 도시에서 다른 도시로 이동할 때에는 비행기를 타고 이동해야 하는데, 때로는 비행 항로가 개설되지 않았을 수도 있다. 또한 당신은 비행기를 아무렇게나 타려는 것이 아니라, 최대한 맛있는 기내식만 먹으면서 이동하려 한다(사실 이게 여행의 목적이다).

항로 개설 여부와 해당 항로에서 제공되는 기내식의 점수가 주어졌을 때, 먹게 되는 기내식의 점수의 총 합이 최대가 되도록 하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 10,000)가 주어진다. 이는 a번 도시에서 b번 도시로 이동하는 항로가 있고, 서비스되는 기내식의 점수가 c점이라는 의미이다. 서쪽에서 동쪽으로 이동하는 항로가 입력될 수도 있고, 같은 도시 쌍 사이에 항로가 여러 개 있을 수도 있지만, 날아다니다 다시 원래 도시로 돌아오는 a=b 와 같은 입력은 없다.

출력

첫째 줄에 기내식 점수의 총 합의 최댓값을 출력한다.

풀이 과정

다이나믹 프로그래밍에 그래프 이론을 사용해 풀이하는 문제이다.

dp[i][j] : i 번 도시에 j 번 이동해서 도달했을 때 기내식 점수의 총 합

 

import sys
input = sys.stdin.readline

n, m, k = map(int, input().rstrip().split())
graph = [{} for _ in range(n+1)]
for _ in range(k):
    a, b, c = map(int, input().rstrip().split())
    if a > b: continue
    if graph[b].get(a, -1) == -1: graph[b][a] = c
    else: graph[b][a] = max(graph[b][a], c)

dp = [[-1 for _ in range(m)] for _ in range(n+1)]
dp[1][0] = 0
for i in range(2, n+1):
    for j in range(m-1):
        for k, v in graph[i].items():
            if dp[k][j] != -1:
                dp[i][j+1] = max(dp[i][j+1], dp[k][j] + v)

print(max(dp[n]))