boj_1149_RGB거리

https://www.acmicpc.net/problem/1149 <풀이> DP가 정말 오랜만이라 잘 풀 수 있을까 걱정됐는데, 풀이 방법이 생각보다 빨리 떠올랐다. (예전에 비슷한 유형을 몇 개 풀어봐서 그런듯 하다.)

문제를 간략하게 설명하자면, N개의 집을 색칠을 할건데, 이웃한 집들은 다른색으로 색칠하고자 한다. 이 때 최소비용을 구하는 문제이다.

(조건 1,2,3을 모두 합쳐서 생각해보면 결국 이 말인 거 같다.) 위 사진은 TC4번을 나타낸 것이다.

문제 조건을 다시 살펴보면, i 번째 집의 색은 i - 1번째 집의 색과 달라야한다. 2번 집에 빨강색, 초록색, 파랑색중 어느 색을 칠해야 정답이 될지 우리는 모른다. 하지만 각 케이스마다 최소값을 구할 수..........