DP (1) 썸네일형 리스트형 [C4] 1149 - RGB거리 문제풀이DP를 이용해 직전 집을 칠하는 데 드는 비용의 최솟값으로부터 현재 집을 칠하는데 필요한 비용을 계산한다.예를 들어 직전 집을 칠하는데 각각 100, 200, 300원이 들었고, 지금 집을 빨간색으로 칠하는데 50원이 든다면직전 집들을 칠하는 비용 + 지금 집을 빨간색으로 칠하는데 드는 비용을 비교해서 집을 빨간색으로 칠하는데 드는 최소 비용을 찾아준다.위 예시에서는 150, 250, 350중 최솟값인 150원이 이 집을 빨간색으로 칠하는데 드는 비용이다.이 조건만 보면 간단한 dp로 해결 할 수 있다. 하지만 주의해야 할 것은 직전 집과 같은 색상으로는 칠할 수 없다는 조건이 붙어있다. 이전 집을 빨간색으로 칠했다면, 다음 집은 빨간색이 아니라 초록색 또는 파란색으로밖에 칠할 수 없다는 것이다... 이전 1 다음
