[백준] [DP] 1149 : RGB 거리

 

[백준] 1149 : RGB 거리

필요 지식

 - dynamic programming

해결 방법

(가정)

 - cost : 각각의 집을 칠하는 비용  

    ex) cost[1][0] : 1번집을 R로 칠하는 cost

 - sub : 현재 집까지 칠하는 최소 비용 

    ex) sub[3][2] : 3번집을 B로 칠했을 때 1,2번 집 cost포함 최소 비용

(해결)

편의 상 0을 R, 1을 G, 2를 B로 나타낸다면 sub를 아래와 같이 나타낼 수 있음.

 - sub[현재 집][R] = min(sub[바로 전 집][G], sub[바로 전 집][B]) + cost[현재 집][R]

즉, 일반화 한다면

 - sub[i][0] = min( sub[i-1][1], sub[i-1][2]) + cost[i][0]

참고한 사이트

https://m.blog.naver.com/occidere/220785383050