BOJ 1149 RGB거리

다이나믹 프로그래밍 입문과도 같은 문제이다

아마 dp처음 풀면 그리디로 풀려고 할텐데 그러면 무조건 오답이다! 왜냐하면 그리디로는 모든 조건들이 최소인 경우를 계산할 수 없기 때문이다.

 

일단, 문제에서 주어지는 RGB 거리 정보를 저장할 배열 dp와, 문제를 풀 배열 solve를 생성했다.

그리고 해당 문제의 점화식은

solve[i][j] = dp[i][j] + get_min(solve[i-1][j-1],solve[i-1][j-2])

이다.

점화식은 잘 보면 이해가 쉽게 갈 것이다. dp[i][j]는 solve[i][j] 자리의 기본 값이고, get_min ~ 을 통해서 같은 색깔 sovle[i-1][j] 를 빼고 두 색깔중에 가장 작은 값을 solve에 더해주는 것이다. 이런식으로 이전의 solve도 계산 되었기 때문에 가장 작은 값이라는 것을 알 수 있을 것이다. 

solve의 베이스 케이스인 sovle[0][0] solve [0][1] solve[0][2]는 그냥 dp[0][0] dp[0][1] dp[0][2]를 대입해주면 된다

 

즉, solve[i][j]에는 dp[i][j]와 더했을 때 가장 작은 값을 더하여, solve[i][j]의 자리에서 도출 될 수 있는 가장 작은 값을 저장한다. -> 이걸 맨 끝까지 반복한다. 

이에 따라 쭉 계산해주고 , 마지막에 배열 solve[n-1] 에서 최솟값을 찾아주면 된다.

 

#include <iostream>
using namespace std;
int dp[1001][3] = { 0 };
int solve[1001][3] = { 0 };
int get_min(int n, int m) {
	if (n < m) return n;
	else return m;
}

int rgb(int n) {
	for (int i = 0; i < 3; i++)
		solve[0][i] = dp[0][i];
	for (int i = 1; i < n; i++) {
		solve[i][0] = dp[i][0] + get_min(solve[i - 1][1], solve[i - 1][2]);
		solve[i][1] = dp[i][1] + get_min(solve[i - 1][0], solve[i - 1][2]);
		solve[i][2] = dp[i][2] + get_min(solve[i - 1][0], solve[i - 1][1]);
	}
	return get_min(get_min(solve[n - 1][0], solve[n - 1][1]), solve[n - 1][2]);

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