[C] 백준 1149번 RGB거리

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

문제

---

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

아이디어 스케치

---

문제에서 주어진 3가지 조건을 만족하면서 시간초과가 발생하지 않게 모든 집을 칠하는 비용의 최솟값을 구하기 위해서는 동적계획법 알고리즘을 사용해야 한다.

i번째 집을 기준으로 색을 칠하는 경우의 수를 살펴보면

i번째 집이 0번색인 경우에는 i-1번째 집의 색은 1번 or 2번이 가능하다.
i번째 집이 1번색인 경우에는 i-1번째 집의 색은 0번 or 2번이 가능하다.
i번째 집이 2번색인 경우에는 i-1번째 집의 색은 0번 or 1번이 가능하다.

위 3가지 경우 중 가장 작은 값을 가지는 경우가 i번째 집까지 구한 비용의 최솟값이다.

위에서 구한 로직을 코드로 작성하면 문제를 해결할 수 있다.

전체 코드

---

#include <stdio.h>
#define min(a,b) a > b ? b : a

int dp[1001][3];

int main() {
	int n;
	int ans;

	scanf("%d", &n);	// 집의 개수를 입력 받음

	for (int i = 0; i < n; i++)
		for (int j = 0; j < 3; j++)
			scanf("%d", &dp[i][j]);		//각 집마다 색깔별로 드는 비용을 입력 받음

	for (int i = 1; i < n; i++) {
		dp[i][0] += min(dp[i - 1][1], dp[i - 1][2]);	// i번째 집을 0번색으로 칠하는 경우(i-1번째 집의 색은 1번색 or 2번색을 선택해야 함)
		dp[i][1] += min(dp[i - 1][0], dp[i - 1][2]);	// i번째 집을 1번색으로 칠하는 경우(i-1번째 집의 색은 0번색 or 2번색을 선택해야 함)
		dp[i][2] += min(dp[i - 1][0], dp[i - 1][1]);	// i번째 집을 2번색으로 칠하는 경우(i-1번째 집의 색은 0번색 or 1번색을 선택해야 함)
	}

	ans = min(dp[n - 1][0], (min(dp[n - 1][1], dp[n - 1][2])));		// 3가지 경우 중 가장 작은 값을 결과값으로 저장

	printf("%d", ans);		// 결과 출력

	return 0;
}

제출 결과

---