99클럽 코테 스터디 14일차 TIL + DP

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

# 17484 진우의 달 여행 (small)

import sys
input = sys.stdin.readline

N, M = map(int,input().split())
fuel_list = [list(map(int,input().split())) for _ in range(N)]
min_fuel_list = [[[float('inf')] * 3 for _ in range(M)] for _ in range(N)]

for i in range(M):
    min_fuel_list[0][i] = [fuel_list[0][i],fuel_list[0][i],fuel_list[0][i]]

for i in range(1,N):
    for j in range(M):
        for k in range(3):
            if (j == 0 and k == 2) or (j==M-1 and k == 0):
                continue
            for l in range(3):
                if k == l :
                    continue
                min_fuel_list[i][j][k] = min(min_fuel_list[i][j][k], min_fuel_list[i-1][j-k+1][l] + fuel_list[i][j])

min_fuel = 1e9
for i in range(M):
    min_fuel = min(min(min_fuel_list[N-1][i]), min_fuel)
print(min_fuel)

• 각각의 위치값을 저장할 때 사용하는 리스트에 방향을 담아야 한다.
• 이전 위치에서 왼쪽대각선, 아래, 오른쪽대각선 중 어느 방향에서 오는지 알아야 한다.
• 이전 값 중 최소값을 가져오기 때문에 dp를 사용한다.