[백준1149] / RGB거리 - DP

 

백준1149

 

 

푼 날짜 : 2024.09.13

푼 문제 : [1149] / RGB거리

사용한 언어 : python

알고리즘 : DP

 

 

점화식 :

dp[i][0] = colors[i][0] + min(dp[i-1][1], dp[i-1][2])
dp[i][1] = colors[i][1] + min(dp[i-1][0], dp[i-1][2])
dp[i][2] = colors[i][2] + min(dp[i-1][0], dp[i-1][1])

 

 

 

초기값은 dp[0]을 colors[0]을 넣어주고 시작했다.

그리고 dp테이블을 하나씩 채워나가는데, i번째의 0번째 요소를 채우기 위해서는 i-1번째의 0번이 아닌 1번과 2번 중 더 작은 값을 더해서 채워준다. 이렇게 해야 값을 최소로 만들며 더해갈 수 있기 때문이다.

 

 

 

(내)이해를 돕기위한 그림

 

 

코드 :

import sys

N = int(sys.stdin.readline())
colors = []
dp = [[0 for _ in range(3)] for _ in range(N)]

for i in range(N):
    color = list(map(int, sys.stdin.readline().split()))
    colors.append(color)

dp[0] = colors[0]
for i in range(1, N):
    dp[i][0] = colors[i][0] + min(dp[i-1][1], dp[i-1][2])
    dp[i][1] = colors[i][1] + min(dp[i-1][0], dp[i-1][2])
    dp[i][2] = colors[i][2] + min(dp[i-1][0], dp[i-1][1])

print(min(dp[-1]))

 

 

생각보다 쉬웠던 문제였다!

앞으로도 DP에 익숙해지게 열심히 풀어야지...