백준 1149 RGB거리

 

 

 

 

 

 

문제를 보자마자 2학년때 수업시간에 배웠던 내용이 떠올랐다. 

교내 식당 가격표

이틀연속으로 같은 식당에서 먹지 않고 8일간 식사를 하는데 드는 최소비용을 구하는 것이다.

 

단순히 "현재 최소비용을 택하면 되겠지" 하면 틀린다.

 

같은 식당이 2일 연속나오면 안되므로, 택해야 되는 시점이 현재라면 어제의 것을 고려해야한다.

 

따라서 해결방법은, 어떤시점 에서 식당A를 선택하면서 끝났다고 할때, 식당 B 혹은 식당C를 선택하면서 끝났다고 할때, 각각의 최종값에서 가장 최소비용이 되는 것을 택하면 된다.

 

위 식당의 문제를 예를 들어보면, 2일차가 됐을때의 최소값은 C->A, A->C의 7이다.

 

 

3일차가 됐을 때의 최소값은 B->A->C (혹은 C->A->C)의 9이다.

 

이런식으로 8일째 세 식당에서 밥을 먹은 경우 중 누적비용이 가장 적은 것이 정답이 된다.

 

 

다시 문제로 돌아와서,

이 문제도 똑같이 적용하면 된다. 2차원 dp배열을 하나 만들어서 

어떤 시점에서 R, G, B각각으로 칠했을 때 누적비용을 비교해주면 된다.