[백준][동적 계획법 1] No.1149_RGB거리 01
https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
문제도 비교적 짧고 해석하기에 어려운 편은 아니다.
마치 '4색 정리'처럼 이웃하는 집들끼리는 색이 서로 달라야 한다.
그때 빨강, 초록, 파랑에 해당하는 각각의 비용이 주어질 때 최솟값으로 칠하는 비용을 물어보는 문제이다.
처음에는 R, G, B들의 색상이 고정되었고 이를 if 조건문으로 풀면 되는 줄 알았다.
그래서 그냥 싼 비용 2개를 뽑아, 홀수와 짝수에 따라 계산해주면 된다고 생각했다.
예시) R 10 G 15 B 20일 때, 집이 홀수면 RGRGR, 집이 짝수면 RGRG
하지만 예제 입출력을 보니 위의 그림(왼쪽)과 같았다.
각 집마다 RGB 값이 모두 달랐던 것이다.
시간 제한은 0.5초이고, 영락없는 DP 문제임을 확신했다.
오른쪽의 예시를 한번 생각해보았다.
처음 한 숫자에서 시작했다고 보자. 그럼 다음 경우의 수는 2개가 될 것이다.
그리고 그 2개에서 또 각각 2개의 경우의 수로 나뉠 것이고, 그 다음부터는 모든 수를 가는 경우의 수가 존재한다.
위에 사진에서만 봐도 벌써 2 * 4 * 6 * 6 = 288가지이다. 이를 식으로 나타내면 {2 * 4 * 6 * (N-2)}와 같다.
문제 입력 제한에서 N이 최대 1000이고 RGB 각각을 모두 확인한다고 했을 때, 최악의 경우는 143,712번이다.
└ 3 * {2 * 4 * 6 * (1000-2)}
내가 갈 수 있는 경우에서 제일 작은 수를 더하면 되는 것 아닌가?라고 생각했다.
예를 들어 집이 3개고 각각 RGB가 다음과 같다.
H1(1, 10, 10), H2(10, 1, 2), H3(1000, 1, 1000)
천천히 아이디어를 따라 풀어보자.
H1에서 가장 적은 비용인 1을 선택했다. 그럼 H2에서는 첫 번째 인덱스는 넘어가야하므로 1과 2중 고민을 할 것이다.
내가 생각한 아이디어는 "갈 수 있는 경우에서 제일 작은 수"이기에 1을 골라야 한다.
자 이제 문제가 생긴다.
H3에서 두 번째 인덱스를 고르지 못하기에, 무조건 1000을 골라야 한다.
이 경우는 H2에서 2라는 손해를 감수하더라고 H3에서 1을 골라야 최소 선택이 된다.
다다음의 경우의 수를 고려하지 못한다는 점에서 '이게 정말 최소 선택 알고리즘인가'하는 문제가 발생한다.