백준 / 다이나믹 프로그래밍 / 1149번 / RGB거리 / C++

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때,

아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는

비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

예제 입력 1 

3

26 40 83

49 60 57

13 89 99

예제 출력 1 

96

 

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int cost = 0;
	int n;
	cin >> n;
	
	int rgb[n][3] = {0,};
	int dp[n][3] = {0,};
	
	for(int i=1; i<=n; i++) {
		for(int j=0; j<3; j++) {
			cin >> rgb[i][j];
		}
	}
	
	for(int i=1; i<=n; i++) {
		dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + rgb[i][0];
		dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + rgb[i][1];
		dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + rgb[i][2];
	}
	
	int result;
	result = min({dp[n][0], dp[n][1], dp[n][2]});
	
	cout << result << '\n';
	
	return 0;
}

---

2차원 배열로 나타낼 생각만 하면 쉬운문제이다.

dp배열은 최솟값을 저장하는 배열이다.

dp[n][0]은 첫번째 행이 1행이라고 했을시 n번째 행중에서 rgb에서 0번째 즉, r로 칠해야할때 최솟값을 나타낸다.

dp[n][1]은 첫번째 행이 1행이라고 했을시 n번째 행중에서 rgb에서 1번째 즉, g로 칠해야할때 최솟값을 나타낸다.

dp[n][2]은 첫번째 행이 1행이라고 했을시 n번째 행중에서 rgb에서 2번째 즉, b로 칠해야할때 최솟값을 나타낸다.

 

따라서 예를들어 문제에서 나온 예제를 보면 우리는 dp[3][0]과 dp[3][1]과 dp[3][2]중 최솟값을 찾아서 출력하면 되는

문제이다.

 

0 = r(red), 1 = g(green), 2 = b(blue) 이다.

dp[3][0]을 구하기 위해선 어떻게 해야할까?

dp[3][0]이 나타내는 의미는 3번째 행(3번째 집)을 red로 칠했을때의 최솟값을 의미한다.

따라서 두번째집은 green이나 blue로 칠해야한다.

즉 다시 dp[2][1], dp[2][2]중 최솟값을 구해서 세번째 집을 red로 칠했을때의 가격을 더해주면 되는것이다.

dp[2][1]과 dp[2][2]를 구하는법도 같다.

dp[2][1] = min(dp[1][0], dp[1][2]) + rgb[2][1]

dp[2][2] = min(dp[1][0], dp[1][1]) + rgb[2][2]

위와 같이 구하면된다.

따라서 우리는 일반항을 구할 수 있다.

 

n개의 집을 칠할때 최솟값을 구한다고 하면

dp[n][0] = min(dp[n-1][1], dp[n-1][2]) + rgb[n][0]

dp[n][1] = min(dp[n-1][0], dp[n-1][2]) + rgb[n][1]

dp[n][2] = min(dp[n-1][1], dp[n-1][0]) + rgb[n][2]

처럼 되는것이다.

 

위의 코드가 의미하는 바는 n번째 집을 각각 r,g,b로 칠했을경우 최솟값이다.

 

따라서 우리는 그중에서 또 최솟값을 구해서 출력해주면 된다.