[ 백준 ] 1149번 - RGB거리 (C++)

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

1149번: RGB거리

 

 

[ 문제풀이 ]

 

최대 1000개의 집이 있고, 앞의 건물과 같은 색으로 칠하면 안 된다는 조건이 있습니다. 모든 조합을 뽑아 최솟값을 결정하려면 O(2^1000)이므로 터무니없는 숫자가 나옵니다. 따라서 이 문제는 dp를 활용하여 풀어주었습니다.

 

총 3N개의 배열을 3번만 탐색하면 되므로 O(N*3*3)이라는 시간복잡도가 나옵니다.

 

앞에 칠했던 건물과 같은 색을 칠하면 안되므로 먼저 dp배열의 값들을 INF로 초기화시켜줍니다. 그리고 첫 번째 집의 색깔을 정해줍니다.

 

예를 들어 첫번째 집을 빨강으로 정한다면 그 값을 제외한 모든 값들을 INF로 초기화시키고 첫 집의 빨간 집만 색칠해줍니다.

 

그렇다면 다음 집에서 빨간색으로 집을 칠하려고 할 때 초록색과 파란색 집은 INF로 초기화 되어 있기 때문에 빨간색으로 칠하는 선택지가 사라지게 됩니다. 이러한 방법으로 첫 번째 집의 색깔을 각각 한 번씩 선택해주면 답을 얻어낼 수 있습니다.

 

[ 소스 코드 ]

#include <iostream>
#define INF 987654321
 
using namespace std;
 
int N;
int RGB[1000][3];        //비용을 저장할 배열
int dp[1000][3];        //최솟값을 저장할 배열
 
int main()
{
    cin >> N;
    int ans = INF;
 
    for (int i = 0; i < N; i++) {
        scanf("%d %d %d", &RGB[i][0], &RGB[i][1], &RGB[i][2]);
    }
 
    for (int t = 0; t < 3; t++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 3; j++) {
                if (i == t && j == 0) {
                    dp[j][i] = RGB[0][i];    //첫 집의 색을 정함
                }
                else {
                    dp[i][j] = INF;            //나머지 집은 INF로 초기화
                }
            }
        }
 
        for (int i = 1; i < N; i++) {        //각 색깔로 칠했을 때 최솟값을 dp에 저장
            dp[i][0] = min(dp[i - 1][1] + RGB[i][0], dp[i - 1][2] + RGB[i][0]);
            dp[i][1] = min(dp[i - 1][0] + RGB[i][1], dp[i - 1][2] + RGB[i][1]);
            dp[i][2] = min(dp[i - 1][0] + RGB[i][2], dp[i - 1][1] + RGB[i][2]);
        }
 
        for (int i = 0; i < 3; i++) {        //마지막에 세 집 중 가장 비용이 적은 집 ans에 저장
            if (ans > dp[N - 1][i]) {
                ans = dp[N - 1][i];
            }
        }
    }
 
    cout << ans;
}