[백준 C++] 17404번: RGB거리 2

1. 문제

https://www.acmicpc.net/problem/17404

17404번: RGB거리 2

 

2. 알고리즘 분류

• 다이나믹 프로그래밍

 

3. 소스 코드

Key Point)
1. 다이나믹 프로그래밍을 통해 최소 비용을 구해 나간다.
2. 빨강 or 파랑 or 초록 시작으로 총 3가지 경우의 수를 각자 계산해 나간다.

 

 

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX 987654321;
int rgb[1000][3];
int dp[1000][3];

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 집의 수(N) 입력
	int N;
	cin >> N;

	// 빨강, 초록, 파랑 비용 입력
	for (int i = 0; i < N; i++) 
		cin >> rgb[i][0] >> rgb[i][1] >> rgb[i][2];

	int ans = MAX;

	// 빨강 or 초록 or 파랑 시작 (총 3번 경우의 수 계산)
	for (int i = 0; i < 3; i++)
	{
		// 시작 색을 제외하고는 비용을 MAX로 지정하여, 계산하지 않게 설정
		for (int j = 0; j < 3; j++)
		{
			if (i == j) dp[0][j] = rgb[0][j];
			else dp[0][j] = MAX;
		}

		// 이전 색을 제외하고 가장 작은 비용의 색을 선택하여 더하기
		for (int j = 1; j < N; j++)
		{
			dp[j][0] = rgb[j][0] + min(dp[j - 1][1], dp[j - 1][2]);
			dp[j][1] = rgb[j][1] + min(dp[j - 1][0], dp[j - 1][2]);
			dp[j][2] = rgb[j][2] + min(dp[j - 1][0], dp[j - 1][1]);
		}

		// 시작 색을 제외하고 발생한 비용 중에서 가장 작은 비용을 ans에 갱신
		for (int j = 0; j < 3; j++)
		{
			if (i == j) continue;
			else ans = min(ans, dp[N - 1][j]);
		}
	}

	// 정답 출력
	cout << ans;

	return 0;
}