[C++] 백준 1149 - RGB거리(점화식 활용)

0. 주어진 문제

RGB거리 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.5 초 (언어별 추가 시간 없음)	128 MB	30515	13669	10229	46.455%

문제

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

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

입력

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

출력

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

예제 입력 1 

3
26 40 83
49 60 57
13 89 99

예제 출력 1 

96

1. 풀이

입력받은 수들을 점화식을 활용해 해결을 해보았다.

각 단계를 나눠, i번째 집에 R,G,B를 칠하게 됐을 때의 최솟값을 구하는 것을 기초로 삼아 bottom-up 형식으로 구현을 하였다.

1) 초기값을 부여한다.

cost[1][0] = (첫번째 R 비용)

cost[1][1] = (첫번째 G 비용)

cost[1][2] = (첫번째 B 비용)

을 초기값으로 한다.

2) 다음단계의 점화식은

cost[2][0] = (두번째 R 비용) + Max(cost[1][1], cost[1][2])

cost[2][1] = (두번째 G 비용) + Max(cost[1][0], cost[1][2])

cost[2][2] = (두번째 B 비용) + Max(cost[1][0], cost[1][1])

3) K단계의 점화식은

cost[K][0] = (K번째 R 비용) + Max(cost[K-1][1], cost[K-1][2])

cost[K][1] = (K번째 G 비용) + Max(cost[K-1][0], cost[K-1][2])

cost[K][2] = (K번째 B 비용) + Max(cost[K-1][0], cost[K-1][1])

이런 형태의 점화식을 구현하여 완성시켰다.

2. 소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int cost[1001][3];
 
//구현은 했는데, 사실 생각해보니 입력을 받으면서 모두 처리가 가능해서 주석으로 남겨두었다.
//void min_cost(int N) {
//    for (int i = 1; i <= N; i++) {
//        cost[i][0] += min(cost[i - 1][1], cost[i - 1][2]);
//        cost[i][1] += min(cost[i - 1][0], cost[i - 1][2]);
//        cost[i][2] += min(cost[i - 1][0], cost[i - 1][1]);
//    }
//     
//}
 
int main() {
    int N;
    cin >> N;
    int temp[3];
    for(int i=1;i<=N;i++) {
        cin >> temp[0] >> temp[1] >> temp[2];
        //점화식 형태로 입력받은 수들을 처리해주자.
        cost[i][0] = temp[0] + min(cost[i - 1][1], cost[i - 1][2]);
        cost[i][1] = temp[1] + min(cost[i - 1][0], cost[i - 1][2]);
        cost[i][2] = temp[2] + min(cost[i - 1][0], cost[i - 1][1]);
    }
    cout << min(min(cost[N][0], cost[N][1]), cost[N][2]);
}

3. 문제 출처

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

4. 참고