[백준/BOJ] 1149 - RGB거리 (c++) (DP)

 

https://www.acmicpc.net/problem/1149

 

기본적인 DP문제입니다.

 

문제를 푸는 아이디어는 집을 색칠할 수 있는 3가지 색깔의 경우의수를 모두다 구해보는 것입니다.

 

코드로는

 

for (int i = 1; i < N; i++) {
	dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + input[i][0];
	dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + input[i][1];
	dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + input[i][2];
}

이렇게 될것입니다. 

 

dp[i][j]는 i번째 집을 j색깔로 칠했을때의 최소비용입니다.

 

따라서 dp[i][0]은 i번째 집을 0번 페인트로 칠했을때 비용 + i-1번째 집을 1번 페인트나 2번 페인트 칠한 둘 중의 최소값이랑 똑같습니다.

---

소스코드

#include <iostream>
#include <algorithm>

using namespace std;

int N, input[1000][3], dp[1000][3], ans=1000006;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) cin >> input[i][0] >> input[i][1] >> input[i][2];
	for (int i = 0; i < 3; i++) dp[0][i] = input[0][i];
	for (int i = 1; i < N; i++) {
		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + input[i][0];
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + input[i][1];
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + input[i][2];
	}
	for (int i = 0; i < 3; i++) ans = min(ans, dp[N - 1][i]);
	cout << ans;
}