안녕하세요. 

풀이 알고리즘을 고민하다 문의 글을 남기게 되었습니다.

동적 계획법으로 문제를 푸는 경우,

n 단계 검토 시, n-1 단계의 합에 현 단계에서 최소가 되는 color를 선택하는 

알고리즘으로 풀이하는 것으로 알고 있습니다.

다만, 아래와 같이 n+1 단계에서의 큰 변화가 있는 경우는

적용이 어렵지 않을까 하는데,

제가 어떤 것을 놓치고 있는지 궁금하여 글을 남깁니다.

집 개수 : 4

1 단계 RGB cost : 1        1         1

2 단계 RGB cost : 20      10       30

3 단계 RGB cost : 1        200     100

4 단계 RGB cost : 1        1,000   1,000

알고리즘 적용: (1 단계, G) 1 + (2 단계, R) 20 + (3 단계, B) 100 + (4 단계, R) 1 = 122

실제 달성 가능 최소 cost: (1단계, R or B) 1 + (2단계, G) 10 + (3단계, B) 100 + (4 단계, R) 1 = 112

감사합니다.