백준 17404번 파이썬 문제풀이(RGB거리 2) - 탑다운(top-down) dp

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

17404번: RGB거리 2

---

아무리 구글링을 해도 바텀업으로만 풀었지 탑다운으로 푼 글이 없어서 탑다운으로 한번 풀어보았다.

 

3차원 메모제이션을 활용해서 풀었으며 마지막전에서 시작 번호와 같은지만 잘 비교해서 같다면 continue해버리는 느낌으로만 하면 쉽게 해결할 수 있다.

 

import sys

sys.setrecursionlimit(5000)

N = int(input())
house = [list(map(int, input().split())) for _ in range(N)]

dp = [[[1 << 30] * 3 for _ in range(3)] for _ in range(N)]


def recur(row, col, first_col):

    if row == N:
        return 0

    if dp[row][col][first_col] != 1 << 30:
        return dp[row][col][first_col]

    for j in range(3):
        if j == col:
            continue
        elif row == N - 2 and j == first_col:
            continue
        dp[row][col][first_col] = min(dp[row][col][first_col], recur(row + 1, j, first_col) + house[row][col])

    return dp[row][col][first_col]


ans = 1 << 30
for i in range(3):
    ans = min(ans, recur(0, i, i))

print(ans)