[백준 1149] RGB 거리

 

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 987654321
using namespace std;

int cost[1002][3];
int dp[1002][3];
//int coin[101] = { 0, }, num_coin[10009] = { 0, };
int N;

int main() {
	cin >> N;
	int a, b, c;
	for (int i = 1; i <= N; i++) {
		cin >> a >> b >> c;
		cost[i][0] = a;
		cost[i][1] = b;
		cost[i][2] = c;
	}
	for (int i = 0; i < 3; i++) {
		dp[1][i] = cost[1][i];
	}
	for (int i = 2; i <= N; i++) {
		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];
	}
	//cout << dp[N][0] << " " << dp[N][1] << " " << dp[N][2] << "\n";
	int ans = min(dp[N][0], dp[N][1]);
	ans = min(ans,  dp[N][2]);
	cout << ans;
}

dp로 풀리는 문제이다.

cost[i][j]는 i번째 집에 j번째 색을 칠하는 cost이고

dp[i][j]는  i번째 집에 j 번 색을 칠하는비용을 뜻한다.

식은 dp[i][j] = dp[i-1][not j] + cost[i][j]이다