[baekjoon 1149] RGB거리 (DP) (C++)

www.acmicpc.net/problem/1149

1149번: RGB거리

문제는 빨강, 초록, 파랑으로 칠해져 있는 집 적혀있는 숫자의 합이 최소가 되도록 구하는 것이다.

규칙은 i번째 집은 i-1번째 또는 i+1번째 집과 같은 색으로 칠해져 있으면 안 된다.

즉, 만약 1번을 뽑았으면 다음 차례엔 1번을 뽑지 못한다는 것이다.

 

나는 3중 dp배열을 통해서 문제를 해결하려 했다.

dp[i][n]에서 n은 각각 1번째, 2번째, 3번째 집을 의미하며 각각을 선택했을 경우 최소가 되는 경우를 저장하는 배열이다.

 

1. i가 1일 경우

각각 n이 1, 2, 3일 땐 집이 하나씩이므로 각자 1, 2, 3에 해당하는 집을 선택하는 경우가 최소일 것이다.

 

2. i가 2 이상일 경우

 - n이 1인 경우 : 1번 집을 선택했다는 것이다 => 이전에 1번 집을 선택하면 안 되므로 이전 최솟값을 저장해둔 배열에서 2번 혹은 3번을 뽑은 경우 중 최솟값을 더해줘야 한다.

 

 - n이 2인 경우 : 2번 집을 선택 => 이전에 2번 집을 선택하면 안 되므로 dp[i-1][0]과 dp[i-1][2]중 최솟값을 더해줘야 한다.

 

- n이 3인 경우 : 3번 집을 선택하는 경우이므로 마찬가지로 이전에 1,2번 중에 선택해야 한다.

 

즉,

1. dp[i][0] = arr[i][0] + min(dp[i-1][1], dp[i-1][2]); // 1번째 집을 선택할 때의 최솟값 = 1번째 집 값 + 이전 2,3번 중 최소
2. dp[i][1] = arr[i][1] + min(dp[i-1][0], dp[i-1][2]); // 2번째 집을 선택할 때의 최솟값 = 2번째 집 값 + 이전 1,3번 중 최소
3. dp[i][2] = arr[i][2] + min(dp[i-1][0], dp[i-1][1]); // 3번째 집을 선택할 때의 최솟값 = 3번째 집 값 + 이전 1,2번 중 최소

 

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1001][3], n, arr[1001][3];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> arr[i][j];
		}
	}

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

	cout << min(min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
}

 

+ 처음에는 각각의 n에 해당하는 자리에 n이 선택되는 경우를 넣어야 하는데 그럼 3개 중 n이 언제 선택될지를 생각하고 있었다. 반대로 생각해보니 n을 선택해두고 나머지를 최솟값을 더하면 되는 것이었다.