[백준] 17484 진우의 달 여행 (Small) | python

import sys
input = sys.stdin.readline

N,M = map(int, input().split())
fuel = []

for _ in range(N):
    fuel.append(list(map(int, input().split())))

dp = [[[float('inf'),float('inf'),float('inf')] for _ in range(M)] for _ in range(N+1)]

for i in range(M):
    dp[0][i] = [fuel[0][i], fuel[0][i], fuel[0][i]]

for i in range(1, N):
    for j in range(M):
        for k in range(3):
            if (j == 0 and k == 0) or (j == M-1 and k ==2):
                continue
            if k == 0:
                dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-1][1]+fuel[i][j], dp[i-1][j-1][2]+fuel[i][j])        
            elif k == 1:
                dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][0]+fuel[i][j], dp[i-1][j][2]+fuel[i][j])
            else:
                dp[i][j][k] = min(dp[i][j][k], dp[i-1][j+1][0]+fuel[i][j], dp[i-1][j+1][1]+fuel[i][j])

result = 1e9

for i in range(M):
    result = min(result, min(dp[N-1][i]))

print(result)

 

🐨 코드 설명 

• 연료 위치 별로 [float('inf'), float('inf'), float('inf')] 세 방향의 무한대 값을 두었다.
• 방향 별로 똑같은 방향을 제외하여 min 값을 구했다.