발상
1차원 3색 문제다. 비슷한 문제로 2차원 지도에서의 4색 정리가 있다. 집들이 일렬로 있을 때 3가지 색을 사용할 수 있고 인접하는 집끼리는 같은 색을 사용할 수 없을 때 모든 집을 칠하는 최소 비용을 구하는 문제다. 이전 연속합과 비슷하지만 이 문제는 정답에 영향을 미치는 인자가 두 가지이다. 인덱스와 색깔이다. 각 집들은 3가지 색을 칠해질 수 있으므로 각 집들이 각 색으로 칠해졌을 때의 최적값들을 순차적으로 계산해나가며 전체 최적값을 구할 수 있다. 첫번째 집은 기저사례로 각각의 색으로 칠하는 비용이 최적값이다. 이후의 집들을 어떤 색 로 칠하는 최적값은 이전 집을 가 아닌 색으로 칠한 2개의 최적값 중 더 작은 값 + 현재 집을 색 로 칠하는 값이다.
점화식
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n; cin >> n;
vector<vector<int>> dp(n + 1, vector<int>(3)), arr(n + 1, vector<int>(3));
for(int i=1;i<=n;i++) {
for(int j=0;j<3;j++) {
cin >> arr[i][j];
}
}
dp[1] = arr[1]; // 기저 사례
for(int i=2;i<=n;i++) {
for(int j=0;j<3;j++) {
dp[i][j] = min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + arr[i][j]; // 이전 최적값 중, 현재 색과 다른 색으로 칠한 최적값 탐색
}
}
cout << *min_element(dp[n].begin(), dp[n].end());
return 0;
}앞으로도 계속 나오지만 정답에 영향을 미치는 인자와 그 수를 파악하는 것이 DP 문제 풀이의 중요한 포인트다.