[백준 BOJ][C++]1149번 RGB 거리 풀이: DP

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

1149번: RGB거리

 

이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. 

 

dp부터 설정합시다. 

 

최소 비용으로 칠해야하기 때문에, dp를 최소비용으로 설정해나가야 합니다. 

 

dp[n][0] 은 n번째 집을 빨간색(R)로 칠했을 때의 1번째~n번째 집까지의 최소비용

dp[n][1] 은 n번째 집을 초록색(G)로 칠했을 때의 1번째~n번째 집까지의 최소비용

dp[n][2] 은 n번째 집을 파란색(B)로 칠했을 때의 1번째~n번째 집까지의 최소비용

으로 나타냅니다. 

 

만약 두 번째 집에서 빨간색으로 칠하고 싶다면, 첫 번째 집을 초록색, 파란색으로 칠했을 때의 비용 중 최솟값을 선택하여 두 번째 집에서 빨간색으로 칠했을 때의 비용 + 빨간색을 제외한 첫 번째 집에서의 최소 비용을 하면 됩니다. 

 

rgb[n][0], rgb[n][1], rgb[2]를 각각 n 번째 집을 빨간, 초록, 파란색으로 칠했을 때의 비용으로 나타내겠습니다. 

 

즉 점화식은

 

dp[n][0]=rgb[n][0]+(dp[n-1][1]과 dp[n-1][2] 중 최소값)

dp[n][1]=rgb[n][1]+(dp[n-1][0]과 dp[n-1][2] 중 최소값)

dp[n][2]=rgb[n][2]+(dp[n-1][0]과 dp[n-1][1] 중 최소값)

이 됩니다. 

 

#include<iostream>
#include<cstdlib>
#include<vector>

using namespace std;

int dp[1001][3];
int rgb[1001][3];

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	int minsum;

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> rgb[i][0] >> rgb[i][1] >> rgb[i][2];
	}

	for (int i = 0; i < 3; i++) {
		dp[1][i] = rgb[1][i];
	}

	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			if (j == 0) {
				minsum = min(dp[i - 1][1], dp[i - 1][2]);
			}
			else if (j == 1) {
				minsum = min(dp[i - 1][0], dp[i - 1][2]);
			}
			else {
				minsum = min(dp[i - 1][1], dp[i - 1][0]);
			}
			dp[i][j] = rgb[i][j] + minsum;
		}
	}

	minsum = dp[n][0];
	for (int i = 1; i < 3; i++) {
		minsum = min(minsum, dp[n][i]);
	}

	cout << minsum;

	return 0;
}