[BOJ] 백준 17404 RGB거리 2 c++ (dp)

문제 출처 : https://www.acmicpc.net/problem/17404 

17404번: RGB거리 2

---

풀이

https://www.acmicpc.net/problem/1149 의 응용 문제이다.

기존 문제는 마지막 N번집에서 1번집 고려를 하지 않았지만 이번에는 고려해야 한다.

 

마지막 집 -> 첫 집

결국 마지막에서 첫 집을 고려해야 하기에, rgb 반복문을 돌려 첫 집을 어디로 선택할지 순회하며 계산하면 된다.

for(int rgb = 0; rgb <= 2; rgb++){
    for(int i = 0; i <= 2; i++){
        if(i == rgb) 
            dp[1][i] = arr[1][i];
        else 
            dp[1][i] = 987654321;
    }

    ...

    for(int i = 0; i <= 2; i++){
        if (i == rgb) continue;
        else ans = min(ans, dp[N][i]);
    }
}

위 코드처럼 rgb 3개를 반복하며 가장 첫 집을 어디로 선택할지 정한다.

과정이 끝나면 선택한 집이 아닌 집 중 최소 비용을 고른다.

 

DP

중간 dp 과정은 어렵지 않다.

dp[i][j]는 i번째에서 j번째 색을 선택했을때 최소 비용이다.

즉, 만약 dp[i][0]이면 i-1번째에서 1, 2번째 색 중 최소 값에 i번째 0번 색 비용을 더한 값이다.

위 내용을 코드로 구현하면 아래와 같다.

for(int i = 2; i <= N; 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]);
}

---

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int arr[1001][3];
int dp[1001][3];
int ans = 987654321;

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

    cin >> N;

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

	for(int rgb = 0; rgb <= 2; rgb++){
		for(int i = 0; i <= 2; i++){
			if(i == rgb) 
				dp[1][i] = arr[1][i];
			else 
				dp[1][i] = 987654321;
		}

		for(int i = 2; i <= N; 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 <= 2; i++){
			if (i == rgb) continue;
			else ans = min(ans, dp[N][i]);
		}
	}
	cout << ans;
}