백준 알고리즘 1149번 동적계획법 기초

동적 계획법(Dynamic Programming) 기초

* 이웃하는 집과 같은색을 칠하면 안되는 것이 요점 *

첫번째 집이 빨간색일 경우 두번째 집은 초록 or 파랑 색만 색칠 가능하다.

처음에 생각한 풀이 방법은

1번 집의 최소 비용을 결정하고 2번 집의 색과 비용을 결정할 때

어떤 색을 1번에서 선택했는지 넘겨 주려 했지만.. 그 걸 처리하는 과정이 쉽지가 않았다.

인터넷을 통해 힌트얻어

현재의 인덱스(n번째 집)을 기준으로 

각 R , G , B 색을 결정 했을때

n-1 번 집의 비용을 설정하는 방법을 사용하기로 하였다.

자꾸 짤려서 이미지로 대체 할게요..