[백준-파이썬] 1149-RGB거리

문제바로가기

import sys

nums = int(sys.stdin.readline())
house = [list(map(int, sys.stdin.readline().split())) for _ in range(nums)]
# print(house)
dp = [[False]*3 for _ in range(nums)] # 각각 i에서  RGB를 선택했을 때 가지는 최소 값
dp[0] = house[0]
# print(dp)

for i in range(1, nums):
    for c in range(3): # 0:R, 1:G, 2:B
        color = [0, 1, 2]
        color.remove(c)
        dp[i][c] = min(dp[i-1][color[0]], dp[i-1][color[1]]) + house[i][c]
        
print(min(dp[-1]))

i번째 위치에 있을 때, 각각 R G B을 선택했을 때의 최소값을 계산하면 모든 경우의 수를 확인할 수 있다. 이후 마지막 row의 최소값이 정답이 된다.