백준 1149번 파이썬 문제풀이(RGB거리) - DP(탑다운)

---

사실 dp문제들 보면 바텀업으로 접근하기 위해 점화식 찾기가 여간 쉬운일이 아니다. 그래서 무조건적으로 탑다운으로 재귀로 짤려고 노력을 많이한다. 다음 코드도 재귀코드이며 잘 분석해보길 바란다.

 

import sys

sys.setrecursionlimit(50000)

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

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


def recur(row, col):
    if row == N + 1:
        return 0

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

    for i in range(3):
        if row >= 1 and i == col:  # 1행이상부터 다음 열이 현재의 열과 같다면 재귀x
            continue
        dp[row][col] = min(dp[row][col], recur(row + 1, i) + homes[row][col])

    return dp[row][col]


print(recur(0, 0))

-> 한 재귀안에서 한번에 돌아서 계산하기 위해 homes의 첫번째 행에 [0,0,0] 을 추가했다.