[Algorithm]Baekjoon 17404번 :: RGB거리 2

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

17404번: RGB거리 2

 
 
int arr[1001][3];
int n;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        int a, b, c;
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
    }
 
    int answer = 0x3f3f3f3f;
 
    for (int i = 0; i <= 2; ++i) // 처음 색깔 선택.
    {
        int dp[1000][3];
 
        for (int j = 0; j <= 2; ++j)
        {
            if (j == i) dp[0][j] = arr[0][j];
            else dp[0][j] = 0x3f3f3f3f;
        }
 
        for (int j = 1; j < n; ++j)
        {
            dp[j][0] = min(dp[j - 1][1] + arr[j][0], dp[j - 1][2] + arr[j][0]);
            dp[j][1] = min(dp[j - 1][0] + arr[j][1], dp[j - 1][2] + arr[j][1]);
            dp[j][2] = min(dp[j - 1][0] + arr[j][2], dp[j - 1][1] + arr[j][2]);
        }
 
        for (int j = 0; j <= 2; ++j)
        {
            if (j == i) continue;
            answer = min(answer, dp[n - 1][j]);
        }
    }
 
    cout << answer;
}

 

n-1과 n+1을 전부 고려해야 하는 문제이다.

특히나 유의해야할 점은, 1번째 집의 경우 2번째집만 고려해야하는게 아니라 n번째 집도 고려해야 한다.

마찬가지로 n번째 집은 n-1번째 집만 고려해야할게 아니라 1번째 집도 고려해야한다.

 

즉, 집의 형태가 원형으로 이루어졌다고 보면 될것같다.

해결할 방법으로는 그냥 첫번째집을 하나의 색으로 고정시키고 DP테이블을 업데이트하는것이다.

RGB, 즉 3번만 고정시키면 되기때문에 3N->시간복잡도(N)으로 해결할 수 있다.

 

예를들어 아예 처음집 색을 빨간색으로 칠했다 가정하면, N번째까지 DP테이블을 업데이트한다음에 N번째의 빨간색을 제외한 초록,파랑값중 작은값을 정답에 저장하면 된다.

똑같이 처음집 색을 초록,파랑으로 해서 N번째까지 DP테이블 업데이트 후, 처음색깔을 제외한 DP테이블의 값을 정답에 최솟값으로 갱신시키면 된다.