백준 17485 진우와 달 여행 (Large) Python

🐸 문제 정보

17485번: 진우의 달 여행 (Large)

 

🤖 알고리즘

DP

 

⏱️ 풀이 시간

35.48m (failed)

 

📝 풀이

DP는 어렵다... 점화식이 안떠올라서 결국 검색으로 아이디어를 얻었다.

1. 3차원 DP 리스트 선언
   • [row][col][직전 방향]
2. 현재 방향과 다른 방향의 직전 요소들 중, 최솟값을 현재 요소와 더해줌
   • 이 때, 각 행의 0번째 열과 마지막 열의 경우, 직전 방향에 유의해야함
   • 0번째 열은 직전 ↘ 방향이 없다
   • 마지막 열은 직전 ↙ 방향이 없다
3. 마지막 행의 최솟값 출력

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline
INF = sys.maxsize

n, m = list(map(int, input().rstrip().split()))
board = [list(map(int, input().rstrip().split())) for _ in range(n)]
dp = [[[INF] * 3 for _ in range(m)] for _ in range(n)]

for j in range(m):
    dp[0][j] = [board[0][j]] * 3

for i in range(1, n):
    for j in range(m):
        if j != 0:
            dp[i][j][2] = board[i][j] + min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1])
        if j != m - 1:
            dp[i][j][0] = board[i][j] + min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2])
        dp[i][j][1] = board[i][j] + min(dp[i - 1][j][0], dp[i - 1][j][2])

print(min([el for row in dp[-1] for el in row]))