[백준/2157] 여행 (Python)

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

2157번: 여행

 

Difficulty : Gold 4

 

Status : Solved

 

Time : 00:07:21

 

---

 

문제 설명

 

 

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 와 같은 입력은 없다.

 

출력

 

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

입력 예시

 

3 3 5
1 3 10
1 2 5
2 3 3
1 3 4
3 1 100

 

출력 예시

 

10

 

 

---

 

풀이

 

DP로 풀어볼 수 있겠다. 

 

• 경로는 동 -> 서, 즉 숫자가 증가하는 순으로 주어지는 경로만 유효하므로 이들만을 저장한다.
• DP 초기화를 진행한다. 1번째 도시에서 남은 도시 수가 M-1개인 초기 상태는 기내식의 합이 0일 것이다
• i번째 도시에서 j번 더 진행 가능하고, i번째에서 k번째 도시까지 c의 기내식 값을 더할 수 있는 경로가 존재한다면,
  DP[k][j-1] = max(DP[k][j-1], DP[i][j] + c)
  가 성립한다.

사실 문제 지문에 모호한 점이 있다. 과연 N번 도시까지 갈 수 있는 경로가 제대로 주어지겠냐는 것. 이런 모호성을 염두해 두고 단순히 풀이하였을 때도 ac를 띄우는 걸 보면 정답이 존재하는 경우만이 주어지는 모양이다.

 

 

풀이 코드

from collections import defaultdict
import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())

flight_course = defaultdict(list)
for _ in range(K) :
  a, b, c = map(int, input().split())
  if a > b :
    continue
  flight_course[a].append((b, c))

dp = [[-1]*M for _ in range(N+1)]

dp[1][-1] = 0
for i in range(1, N) :
  for j in range(1, M) :
    if dp[i][j] == -1 :
      continue
    for nxt, cost in flight_course[i] :
      dp[nxt][j-1] = max(dp[nxt][j-1], dp[i][j] + cost)

print(max(dp[-1]))

풀이 완료!