먼저 dp[N][3] 이렇게 만들어 줄거다. 행에는 n번째 집, 열에는 RGB의 값을 넣어준다.
dp[0][0]= 1번 집이 R를 색칠했을 경우 비용의 최솟값,
dp[0][1]= 1번 집이 G를 색칠했을 경우 비용의 최솟값,
dp[0][2]= 1번 집이 B를 색칠했을 경우 비용의 최솟값... 을 차례로 저장한다
먼저 처음 dp에 각 집을 R,G,B로 칠하는 비용을 입력받으면서 저장한다.
void input() {
cin >> N;
if (N > MAX)
exit(EXIT_FAILURE);
for (int i = 0; i < N; i++)
for (int j = 0; j < 3; j++)
cin >> dp[i][j];
}
그 다음 dp[0][i] 일 때 값들은 그대로 두고
dp[1][i]값들을 차례로 생각해본다.
dp[1][0]에는 두 번째 집이 R로 칠해졌을 경우이므로, 첫 번째 집이 R이면 안 된다. 그래서 (첫 번째 집이 G로 칠해졌을 경우 + 두 번째 집이 R로 칠해질 경우) 와 (첫 번째 집이 B로 칠해졌을 경우 + 두 번째 집이 R로 칠해질 경우)중 더 작은 값을 저장한다.
#include<iostream>
#include<algorithm>
const int MAX = 1001;
int dp[MAX][3];
int N;
using namespace std;
void input() {
cin >> N;
if (N > MAX)
exit(EXIT_FAILURE);
for (int i = 0; i < N; i++)
for (int j = 0; j < 3; j++)
cin >> dp[i][j];
}
int paintRGB() {
for (int i = 1; i < N; i++) {
dp[i][0] = min(dp[i - 1][1] + dp[i][0], dp[i - 1][2]+dp[i][0]);
dp[i][1] = min(dp[i - 1][0] + dp[i][1], dp[i - 1][2] + dp[i][1]);
dp[i][2] = min(dp[i - 1][0] + dp[i][2], dp[i - 1][1] + dp[i][2]);
}
return min({dp[N - 1][0], dp[N - 1][1], dp[N - 1][2]});
}
int main() {
input();
cout << paintRGB() << endl;
return 0;
}