백준 2157 여행 파이썬 dp풀이

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

2157번: 여행

 

기존에 풀지 못하고 dfs + dp 조합 해설을 확인했었다.

import sys

N, M, K = map(int, sys.stdin.readline().split())
# N: 1-N까지의 도시가 있다.
# M: M개 이하의 도시를 지나는 여행을 계획 중이다
# K: 항로 개수
INF = -sys.maxsize


def solution(idx, cnt):
    global N, M
    if idx != N and cnt == M:
        return INF  # 도달 못 함
    if idx == N:
        return 0
    if dp[idx][cnt] != -1:
        return dp[idx][cnt]
    dp[idx][cnt] = INF
    for i in range(idx + 1, N + 1):
        if arr[idx][i]:
            dp[idx][cnt] = max(dp[idx][cnt], solution(i, cnt + 1) + arr[idx][i])
    return dp[idx][cnt]


arr = [[0] * (N + 1) for _ in range(N + 1)]
dp = [[-1] * (M + 1) for _ in range(N + 1)]
for _ in range(K):
    a, b, c = map(int, sys.stdin.readline().split())
    arr[a][b] = max(arr[a][b], c)
result = solution(1, 1)
print(result)

 

 

dfs + dp 메모이제이션 답안은 머릿속에서 잘 떠오르지 않는다.

그리고 반복문으로 해결할 수 있지 않을까, 생각했다..

 

 

 

먼저 dfs + dp 조합 풀이는 dp[i][j]가 i에서 N까지 도달할 때 j개의 나라를 거쳤을 때 최대 기내식 값이다.

 

여기서, 나는 dp[i][j]가 1에서 i까지 도달할 때 j개의 나라를 거쳤을 떄 최대 기내식 값이라고 두고 문제를 풀 수 없을까 고민했다.

 

i도시에 도달하기 위해서는 더 작은 번호의 나라들만 우선적으로 거쳐야 한다는 점을 명심하고 재귀를 제거하고 반복문을 돌렸다.

import sys

N, M, K = map(int, sys.stdin.readline().split())

arr = [[0] * (N + 1) for _ in range(N + 1)]

for _ in range(K):
    a, b, c = map(int, sys.stdin.readline().split())
    arr[a][b] = max(arr[a][b], c)

dp = [[-float("inf")] * (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 arr[k][i]:
                dp[i][j] = max(dp[i][j], arr[k][i] + dp[k][j - 1])

print(max(dp[-1]))

 

 

dp 초기화를 0으로 했더니 오답이 나왔었다.

이는 i 도시로 아예 도달할 수 없을 때(경로가 없을 때)를 구분하지 못하기 때문이었다.