BOJ 1149 RGB거리(C++)

RGB거리 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	7338	3530	2540	48.997%

문제

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다.

출력

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

예제 입력 

3
26 40 83
49 60 57
13 89 99

예제 출력 

96

힌트

출처

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 다이나믹 프로그래밍

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

#include    <cstdio> #pragma warning (disable : 4996) #define min(x,y) (x) < (y) ? (x) : (y) int D[1111][3]; int C[1111][3]; int main() {     int N;     scanf("%d", &N);       for (int i = 1; i <= N; ++i)         for (int j = 0; j < 3; ++j)             scanf("%d", &C[i][j]);       for (int i = 0; i < 3; ++i)         D[1][i] = C[1][i];       for (int i = 2; i <= N; ++i)     {         D[i][0] = min(D[i - 1][1], D[i - 1][2]);         D[i][0] += C[i][0];         D[i][1] = min(D[i - 1][0], D[i - 1][2]);         D[i][1] += C[i][1];         D[i][2] = min(D[i - 1][1], D[i - 1][0]);         D[i][2] += C[i][2];       }       int min = D[N][0] < D[N][2] ? (D[N][0] < D[N][1] ? D[N][0] : D[N][1]) : (D[N][2] < D[N][1] ? D[N][2] : D[N][1]);     printf("%d", min);       return 0; }

dynamic programing중에서 쉬운문제? 같다. 

사실 다이나믹 프로그래밍 문제의 난이도는 아무래도 점화식을 세우는난이도와 비례하는 것 같은데

이 문제는 점화식 세우기가 상당히 쉬웠던 것 같다. 

D[i][0]은 i번째 집을 빨강으로 칠할 때의 가장 최소 가격

D[i][1]는 i번째 집을 초록으로 칠할 때의 가장 최소 가격

D[i][2]는 i번째 집을 파랑으로 칠할 때의 가장 최소 가격

이라고 생각하면 매우 간단하다. 

결국 이 값은 D[i-1]중에 D[i]번째에 칠할 색을 제외한 나머지 두 색을 칠했을 때의 최소값 + 해당하는 색을 칠할 때의 값을 더하면 D[i][해당색]이 된다.

D[N][0]~D[N][2]중 최소값을 찾으면 답이 된다.