백준 1149 rgb 거리 [python]

실버1

💡아이디어

n개의 집을 rgb로 가지는 2차원 배열을 만들어서 최적 탐색을 한다

https://st-lab.tistory.com/128

 

 

풀이과정

먼저 arr 변수에 n개의 집을 이차원 배열로 만들어준다

rgb 배열의 탐색 할 dp 배열을 초기화 해준 후 반복문을 통해 최솟값을 구하면 된다

 

코드

import sys
input = sys.stdin.readline
n = int(input())

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

dp = [[0] * 3 for _ in range(n + 1)]  # dp[n]까지 만들기 위해 n+1 크기로

dp[0] = [0, 0, 0]  

# 1번째 집부터 n번째 집까지 dp 채우기
for i in range(1, n + 1):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i-1][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i-1][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + arr[i-1][2]

print(min(dp[n]))