[Baekjoon/백준][17404][C/C++] RGB거리 2

『목차』
0. 개요
1. 문제
2. 풀이
3. 코드

0. 개요

동적 프로그래밍(Dynamic Programming) 문제. 1149번 RGB거리 문제와 세트문제이다.

RGB거리1(1149번)문제는 선형배치문제라 할 수 있고, RGB거리2(17404번)문제는 원형배치문제라 할 수 있다.

1. 문제

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

17404번: RGB거리 2

[문제]

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

[입력]

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

[출력]

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

[예제 입력 1]

3
26 40 83
49 60 57
13 89 99

[예제 출력 1]

110

[예제 입력 2]

3
1 100 100
100 1 100
100 100 1

[예제 출력 2]

3

[예제 입력 3]

3
1 100 100
100 100 100
1 100 100

[예제 출력 3]

201

[예제 입력 4]

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

[예제 출력 4]

208

[예제 입력 5]

8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

[예제 출력 5]

253

반응형

2. 풀이

https://lumir.tistory.com/47

[Baekjoon/백준][1149][C/C++] RGB거리

 

백준 1149번(RGB거리)의 응용버전이다. 1149번 문제를 풀고 오면 문제풀이가 좀 더 수월하다.

기존 1149번 문제와 달리 하나의 조건이 더 추가되었다. 처음과 마지막집의 색이 달라야 한다는 점이다. 이 조건으로 인하여 첫번째 집과 마지막 집이 서로 이웃이 되어, 1149번(RGB거리) 문제는 선형배치, 17404번(RGB거리 2)문제는 원형배치 문제라 판단할 수 있게 되었다.

 

선형 문제의 경우, 색칠을 시작해야 하는 시작점이 명확하다. 또한, 처음과 마지막 집 사이의 색 중복을 고려하지 않아도 되었기 때문에, 한번의 DP과정을 통해 문제를 해결할 수 있었다.

 

원형 문제의 경우, 색칠을 시작해야 하는 시작점이 명확하지 않다. 따라서, 어떤 집 하나를 임의로 시작점으로 잡은 뒤 색을 칠해나가야 한다. 또한, 처음과 마지막 집의 색상이 달라야 하므로, 처음 시작점의 색을 R, G, B중 하나로 고정시켜놓고 1149번(RGB거리) 문제 때 사용한 DP과정을 이용해야 한다. 처음 집이 R, G, B일 때, 각각의 경우의 수를 살펴보면 다음과 같다.

 

X. 1번집이 R이고 마지막집이 R일때 최소비용

1. 1번집이 R이고 마지막집이 G일때 최소비용

2. 1번집이 R이고 마지막집이 B일때 최소비용

3. 1번집이 G이고 마지막집이 R일때 최소비용

X. 1번집이 G이고 마지막집이 G일때 최소비용

4. 1번집이 G이고 마지막집이 B일때 최소비용

5. 1번집이 B이고 마지막집이 R일때 최소비용

6. 1번집이 B이고 마지막집이 G일때 최소비용

X. 1번집이 B이고 마지막집이 B일때 최소비용

위 경우의 수 중에서, 1번집과 마지막집의 색상이 같은 경우는 문제의 조건에 의해 오답이 되므로, 경우의 수에서 제외하였다.

 

DP과정을 그림으로 살펴보면 다음과 같다. (Bottom Up 방식으로 DP를 진행하였다.)

[Baekjoon/백준][17404][C/C++] RGB거리 2

 

3. 코드

/* 좀 더 간단한 풀이 : 0번 idx 기본세팅. 1번 idx부터 DP 계산 시작. */
#pragma warning(disable:4996)
#include <cstdio>
#include <climits>
#include <algorithm>
#define INF (INT_MAX / 2)
using namespace std;

int table_src[1000][3] = {}; //R=0, G=1, B=2

int main(int argc, char* argv[]) {
	/* Input */
	int N; scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d %d %d", &table_src[i][0], &table_src[i][1], &table_src[i][2]);

	/* DP */
	int ans = INF;
	for (int i = 0; i < 3; i++) {
		/* Init */
		int table_dp[1000][3] = {};

		/* i번 집에 지정된 색 이외의 색은 MAX로 지정하여 dp할때 선택되지 않도록 함. */
		table_dp[0][(i) % 3] = table_src[0][(i) % 3];
		table_dp[0][(i + 1) % 3] = INF;
		table_dp[0][(i + 2) % 3] = INF;

		/* DP */
		for (int j = 1; j < N; j++) {
			table_dp[j][0] = table_src[j][0] + min(table_dp[j - 1][1], table_dp[j - 1][2]);
			table_dp[j][1] = table_src[j][1] + min(table_dp[j - 1][0], table_dp[j - 1][2]);
			table_dp[j][2] = table_src[j][2] + min(table_dp[j - 1][0], table_dp[j - 1][1]);
		}

		/* 최솟값 선택 */
		ans = min({ ans, table_dp[N - 1][(i + 1) % 3], table_dp[N - 1][(i + 2) % 3] });		
	}

	/* Output */
	printf("%d", ans);

	/* End */
	return 0;
}

/* 좀 더 복잡한 풀이 : 0, 1번 idx 기본세팅. 2번 idx부터 DP 계산 시작. */
#pragma warning(disable:4996)
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;

int table_src[1000][3] = {}; //R=0, G=1, B=2

int main(int argc, char* argv[]) {
	/* Input */
	int N; scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d %d %d", &table_src[i][0], &table_src[i][1], &table_src[i][2]);

	/* DP */
	int ans = INT_MAX;
	for (int i = 0; i < 3; i++) {
		int table_dp[1000][3] = { table_src[0][0], table_src[0][1], table_src[0][2] };

		table_dp[1][(i) % 3] = INT_MAX;
		table_dp[1][(i + 1) % 3] = table_dp[0][(i) % 3] + table_src[1][(i + 1) % 3];
		table_dp[1][(i + 2) % 3] = table_dp[0][(i) % 3] + table_src[1][(i + 2) % 3];

		for (int j = 2; j < N; j++) {
			table_dp[j][0] = table_src[j][0] + min(table_dp[j - 1][1], table_dp[j - 1][2]);
			table_dp[j][1] = table_src[j][1] + min(table_dp[j - 1][0], table_dp[j - 1][2]);
			table_dp[j][2] = table_src[j][2] + min(table_dp[j - 1][0], table_dp[j - 1][1]);
		}

		ans = min({ ans, table_dp[N - 1][(i + 1) % 3], table_dp[N - 1][(i + 2) % 3] });
	}

	/* Output */
	printf("%d", ans);

	/* End */
	return 0;
}