ACMICPC 1149 RGB거리
문제
RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다.
또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다.
처음 집과 마지막 집은 이웃이 아니다.
각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때,
모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다.
둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다.
출력
첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.
쉬운것같은데 막상 풀려니 헷갈리고 생각해보니 쉬웠던, 해괴한 문제...
"모든 이웃은 같은 색으로 칠할 수 없다" 라는 제한 때문에 문제 난이도가 조금
올라갔다.
각각의 케이스(집을 R,G,B로 칠할때의 값) 중 최적화된 값이 앞서 계산했던
최저값과 더해질때 위의 제한사항 때문에 해당이 안 되는 경우를 빼줘야 하기때문이다.
예제 입력을 예로 들어보면
R 26 R 49 R 13
G 40 G 60 G 89
B 83 B 57 B 99
1번집에서 R을 선택하였을때, 2번집의 값만을 생각하면 R이 최선의 선택이지만,
제한사항으로 인해 G,B중에서만 선택 해야 한다.
또한 1번집에서 최선의 선택이 R이었다하여도, 2번째 집에서 R값이 1번집의 선택을
상쇄하고 남을정도로 G, B에 비해 값이 싸다면, 1번집에서 차선의 선택이
궁극적으로는 최선의 선택이 될 수도 있다는 소리다.
'매 순간 순간의 최선의 선택이 최종적으로는 최선이 아닐수있다'
라는 걸 염두해두고 코드를 짜야했다.
사실 그래봤자 첫번째 집에서 R,G,B 값을 각각 선택했을때부터
N번째 집까지 각각의 경우의 최선을 구하면 그만이었다.
완전탐색으로 풀기에는 경우수가 생각보다 많고,
그냥 이게 최선인 듯싶다.