[BOJ] 백준 17404번: RGB 거리 2

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

17404번: RGB거리 2

[BOJ] 1149번 RGB 거리 문제에서 조건이 추가된 dp 문제입니다.

 

1번 집의 색과 N번 집의 색이 서로 같지 않아야 합니다.

 

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int N, RGB[1001][3], dp[1001][3][3], ans;

void solve(){
	memset(dp, 0x3f, sizeof(dp));
		
	dp[1][0][0] = RGB[1][0];
	dp[1][1][1] = RGB[1][1];
	dp[1][2][2] = RGB[1][2];	
	
	for(int i = 2; i <= N; ++i){
		for(int j = 0; j < 3; ++j){	
			dp[i][0][j] = min(dp[i-1][1][j], dp[i-1][2][j]) + RGB[i][0];
			dp[i][1][j] = min(dp[i-1][0][j], dp[i-1][2][j]) + RGB[i][1];
			dp[i][2][j] = min(dp[i-1][0][j], dp[i-1][1][j]) + RGB[i][2];
		}
	}
	
	ans = INF;
	for(int i = 0; i < 3; ++i){
		for(int j = 0; j < 3; ++j){
			if(i == j) continue;
			if(ans > dp[N][i][j]) ans = dp[N][i][j];	
		}
	}
	cout << ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	
	for(int i = 1; i <= N; ++i){
		for(int j = 0; j < 3; ++j){
			cin >> RGB[i][j];	
		}
	}
	
	solve();
}

 

dp 문제는 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 일관성있게 풀이합니다.

 

1) table 정의

dp[i][curr][st] : 1번 집의 색이 st색이면서, curr색으로 i번 집을 칠할 때의 최소 비용(st, curr ∈ {0, 1, 2})
(0 : R , 1 : G , 2 : B)

 

처음 table을 설계할 때에는 아래와 같이 설계하였습니다.

dp[i][curr] : curr색으로 i번 집을 칠할 때의 최소 비용(curr ∈ {0,1,2})

(0 : R , 1 : G , 2 : B)

 

다만 이런 방식으로 1번, 2번, 3번, ... , N번 집까지 table을 채워나간 후 *min_element(dp[N], dp[N]+3)을 최소 비용이라고 하기엔 1번 집과 N번 집의 색이 서로 달라야한다는 조건을 고려하지 못한 결과임을 알 수 있습니다.

 

고민한 결과 1번 집의 색을 계속 가져간다면 N번 집의 색을 선택할 때 1번 집의 색과 N번 집의 색이 다른 결과 중에서 최소 비용을 선택할 수 있음을 파악했고 dp table을 처음 제시한 바와 같이 정의했습니다.

 

2) 점화식 찾기

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

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

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

(st ∈ {0, 1, 2})

 

3) 초기값 설정

dp[1][0][0] = RGB[1][0];

dp[1][1][1] = RGB[1][1];

dp[1][2][2] = RGB[1][2];

for(int i = 0; i < 3; ++i){
    dp[1][i][i] = RGB[1][i];
}

위 코드처럼 반복문으로 초기값을 설정할 수도 있겠습니다.

 

정답으로는 dp[N][i][j] 중에서 N번 집에서 칠한 색(i)과 1번 집에서 칠한 색(j)이 같을 경우 문제에서 제시한 조건을 충족하지 못하니 continue로 후보에서 제외하고 나머지 중에서 최소값을 출력해주시면 되겠습니다. (i, j ∈ {0, 1, 2})

 

점화식 중에 min을 사용하기 때문에 적당히 큰 값으로 dp 배열을 초기화할 필요가 있습니다.

집을 칠하는 비용이 1,000보다 작거나 같은 자연수이고 집의 수는 최대 1,000이므로 초기화할 INF값으로 1,000,001 이상의 수를 사용할 수 있습니다. 저는 memset을 사용할 수 있으면서 RGB값을 더하더라도 integer overflow가 발생하지 않을 0x3f3f3f3f값을 INF 값으로 사용했습니다. 

 

실버1 문제 수준에서는 1차원, 2차원 dp 정도로 쉽게 풀 수 있었는데 이번 문제에서는 고려해야할 조건이 추가로 있었기에 table의 차원을 늘림으로써 문제를 해결할 수 있었습니다.

 

시간복잡도는 O(N)입니다.