개발 블로그

문제 링크 : 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보다 작거나 같은 자연수이다.

출력

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

접근 방법

현재 내가 칠할 색을 r,g,b로 각각 세 경우로 나눠서 생각해야한다.

만약 내가 현재 r을 칠한다고 하면, 그 전 집은 g 또는 b로 칠할 수 있다. 

현재 g를 칠한다고 하면, 그 전 집은 r 또는 b로 칠할 수 있다.

현재 b를 칠한다고 하면, 그 전 집은 r 또는 g로 칠할 수 있다.

dp[i][0] 은 i번째 집을 r로 칠하는 경우에, 1~i번째 집을 모두 칠하는데에 드는 최소 비용을 저장하고

dp[i][1] 은 i번째 집을 g로 칠하는 경우에, 1~i번째 집을 모두 칠하는데에 드는 최소 비용을 저장하고

dp[i][2] 은 i번째 집을 b로 칠하는 경우에, 1~i번째 집을 모두 칠하는데에 드는 최소 비용을 저장한다.

문제의 예제로 생각해보자. 아래 표는 dp[][] 이다.

3번째 집을 칠하기까지 최소 비용은 min(96,172,185) = 96이 답이 된다.

처음에는 3가지가 아닌 6가지로 나눠서 생각했었다. (현재 내가 r을 칠하는 경우에 (전에 g, 전전에 b) or (전에 b, 전전에 g) .... 이런식으로) 

그러나 어짜피 dp[i][0]에 값을 저장할 때, i번째에 r을 칠할 때 

1) i-1 번째 g 칠하기

2) i-1 번째 b 칠하기

이렇게 두가지 경우에서 최소 값을 따져서 저장했으므로 6가지로 나눠서 생각할 필요 없이 3가지로만 나눠서 생각하면 되는 것이다.

#include <iostream>
#include <algorithm>

using namespace std;

int rgbArr[1001][3];
int dp[1001][3];

int main(){
    
    int N; cin>>N;

    for(int i = 1; i<=N; i++){
        for(int j = 0; j<=2; j++){
            scanf("%d", &rgbArr[i][j]);
        }
    }
    rgbArr[0][0] = 0;   rgbArr[0][1] = 0;   rgbArr[0][2] = 0;
    dp[0][0] = 0;   dp[0][1] = 0;   dp[0][2] = 0;
    dp[1][0] = rgbArr[1][0];    dp[1][1] = rgbArr[1][1];    dp[1][2] = rgbArr[1][2];

    
    for(int i = 2; i<=N; i++){
        
        dp[i][0] = min(rgbArr[i][0] + dp[i-1][1], rgbArr[i][0] + dp[i-1][2]);
        dp[i][1] = min(rgbArr[i][1] + dp[i-1][0], rgbArr[i][1] + dp[i-1][2]);
        dp[i][2] = min(rgbArr[i][2] + dp[i-1][0], rgbArr[i][2] + dp[i-1][1]);
        
        int mini=1000000; //1000*1000
        for(int j = 0; j<=2; j++){
            mini = min(mini, dp[i][j]);
        }
        
    }
    
    int ans=1000000;
    for(int i = 0; i<3; i++){
        ans = min(ans, dp[N][i]);
    }

    
    cout << ans;
    return 0;
}