[백준] 1149번: RGB거리 [C++]

 

알고리즘 분류: 다이나믹 프로그래밍

문제 링크: https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

 

 

【 풀이 】

 

한층 밑으로 내려갈 때마다 각 칸에 맞는 경우의 수 중에 최솟값을 저장하고 마지막 값들 중 최솟값을 출력해주면 되는 문제이다.

최솟값을 계산해 저장하는 배열을 dp, 원본 배열은 rgb라고 하자.

 

dp[0][0] = rgb[0][0]
dp[0][1] = rgb[0][1]
dp[0][2] = rgb[0][2]

 

가 될 것이다.

 

한층 내려갔을 때는 각 칸마다 경우의 수가 두가지 있다.

 

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

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

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

 

즉, 바로 윗 층의 자신의 칸을 제외한 두칸 중 최솟값과 구하고자 하는 칸의 원래 숫자를 더해서 저장해가면 된다.

이 식을 일반화 하면,

 

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]

 

가 된다.

 

 

【 코드 】

 

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

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

int main() {
	int n;
	cin >> n;

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

	dp[0][0] = rgb[0][0];
	dp[0][1] = rgb[0][1];
	dp[0][2] = rgb[0][2];

	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];
	}

	cout << *min_element(dp[n - 1], dp[n - 1]+3);

	return 0;
}