[BOJ/C++] 1149번 RGB 거리: DP(다이나믹 프로그래밍)

문제 설명

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. 테이블 설정

D[i][0] = i번째 집을 빨간색으로 색칠 했을 때 누적 최소비용

D[i][1] = i번째 집을 초록색으로 색칠 했을 때 누적 최소비용

D[i][2] = i번째 집을 파란색으로 색칠 했을 때 누적 최소비용

2. 초기값 

D[1][0] = R[1]

D[1][1] = G[1]

D[1][2] = B[1]

3. 점화식 세우기

D[i][0] = min (D[i-1][1],D[i-1][2])+R[i];

D[i][1] = min (D[i-1][0] ,D[i-1][2]) + G[i];

D[i][2] = min (D[i-1][1] , D[i-1][0])+B[i];

따라서 i=2 부터 for문을 돌려 각각 D[i][0] , D[i][1] ,D[i][2] 를 구하고

최종적으로 *(min_element(D[N], D[N+3])) 를 통해 누적 최소비용을 구할 수 있다.

코드

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

int D[1000][1000];
int R[1000];
int G[1000];
int B[1000];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N,cost;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> R[i] >> G[i] >> B[i];
	}
	D[1][0] = R[1];
	D[1][1] = G[1];
	D[1][2] = B[1];
	for (int i = 2; i <= N; i++) {
		D[i][0] = min(D[i - 1][1], D[i - 1][2]) + R[i];
		D[i][1] = min(D[i - 1][0], D[i - 1][2]) + G[i];
		D[i][2] = min(D[i - 1][0] , D[i - 1][1]) + B[i];
	}
	cout << *(min_element(D[N], D[N] + 3));
}