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

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

0. 개요

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

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

1. 문제

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

1149번: RGB거리

[문제]

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

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

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-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]

96

[예제 입력 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]

102

[예제 입력 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. 풀이

Bottom Up(상향식) 방식을 통해 풀었다.

table 배열에 갱신되는 값은 아래 그림과 같은 원리를 따른다.

맨 마지막 값이 갱신되면, 배열 제일 아래쪽의 3개의 값 중 최솟값을 구해 출력하면 된다.

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

3. 코드

#pragma warning(disable:4996)
#include <stdio.h>

#define min(a,b) (((a) < (b)) ? (a) : (b))

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

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

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

	/* Output */
	printf("%d", min(table[N][0], min(table[N][1], table[N][2])));

	/* End */
	return 0;
}