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

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

17404번: RGB거리 2

#include <iostream>
#include <algorithm>
using namespace std;
int N;
int arr[1001][3];
int dp[1001][3];
int res = 987654321;
int main(void)
{
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i][0] >> arr[i][1] >> arr[i][2];

	
	for (int Color = 0; Color < 3; Color++) { // Color : 시작집의 색

		for (int i = 0; i < 3; i++) // 시작집 dp[0][i]를 초기화 해줄것인데
		{
			if (i == Color) // 시작 색과 같으면 그 색 비용으로 초기화 해줌
				dp[0][i] = arr[0][i];
			else
				dp[0][i] = 987654321; // 시작집의 색과 다른 색이면 시작집 이후에서 고르지도 못하게 최댓값으로 초기화
		}

		for (int i = 1; i < N; i++) // i번째의 색과 다른 색중 최솟값중 고름 그리고 값 추가
		{
			dp[i][0] = arr[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
			dp[i][1] = arr[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
			dp[i][2] = arr[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
		}

		for (int i = 0; i < 3; i++) // 마지막 집을 고를것인데
		{
			if (i != Color) // 시작집의 색깔과 달라야함 
				res = min(res, dp[N - 1][i]);
		}
	}
	cout << res;
}

대강 풀이를 넓게 보자면

시작 집의 색과 마지막 집의 색이 달라야 하므로

우선 시작 집의 색을 골라주고 시작한다.

그리고 마지막 집 까지 dp를 통해 값을 최솟값으로 갱신해 나가고

첫 번째 집과 마지막 집의 색이 다른 dp 값 중 최솟값을 결괏값 res에 초기화 시켜준다.

 

그래도 이해가 안 간다면!

dp[0]의 시작을 잘 초기화 시켜주는것이 중요하다.

내가 시작 집의 색 Color를 골라주었는데 그 색과 같으면 그 페인트 값으로 초기화 해주고

그게 아니라면 다음번 dp에서(0번째 다음) 고를때 내가 고른 색을 고를 수밖에 없게 해 준다.

( 어떻게? 내가 고른 색이 아니면 큰 값으로 초기화 )

이러면 내가 고른 색 그게 제일 싼 방법이니깐! 고를 수밖에 없다...

그대로 쭉쭉 dp를 해줄 때 내가 처음 골라준 색을 기준으로 DP가 나아가므로 최종 dp에는 시작점 색이

내가 고른 Color인 dp 값이 나오고~ 최종 dp중에서도 시작 색과 다른 dp값을 골라주면 그게 답인 것이다!

 

아래의 코드는 위에서 설명한 dp[0]을 잘 초기화 시켜주는 부분이다 

내가 고른 Color ( 시작 색)과 일치하면 dp[0]의 스타트 값을 그 색을 칠하는 비용으로 초기화 시켜주는것이다.

다른 색이라면 그냥 선택도 안되게 말도 안 되는 큰 값으로 초기화 시켜주는것

for (int i = 0; i < 3; i++)
{
			if (i == Color)
				dp[0][i] = arr[0][i];
			else
				dp[0][i] = 987654321;
}

 

i번째 집이 0의 색일 경우 i-1번째 dp의 1의색과 2의 색 중 최솟값에 i번째 집을 색칠할 색의 비용을 더해준다.

i번째 집이 0의 색이면 다음 집은 0의 색을 제외한 1,2 색만 가능하니깐

dp[i][0] = arr[i][0] + min(dp[i - 1][1], dp[i - 1][2]);