백준 17404번 - RGB거리 2

www.acmicpc.net/problem/17404

17404번: RGB거리 2

DP를 공부했던 사람들이라면 아마 대부분 RGB거리 1을 풀어봤을 것이다.

 

나 역시 RGB거리 1을 얼마 전에 풀어봤고, 어렵지 않게 점화식을 구할 수 있었기에 RGB2에 도전하였다.

 

빨리 풀고 그냥 딴 거 하려 했는데 코드가 생각보다 더럽고..

뭐 일단 맞긴 했는데 정확한 풀이인지 확신이 안 서서

딴 사람들 풀이가 궁금해서 구글링 해봤는데.. 뭔 소린지 모르겠어

이게 컴공의 특성인지 모르겠는데 설명을 정~말 못 하는 것 같아요 ㅎㅎ.. (물론 나도 포함이지만)

 

그래서 내가 이해하고 푼 대로 설명해볼까 한다.

 

문제는 기초 문제와 거의 똑같은데 조건 하나가 추가된다.

 

[RGB1]
1번 집의 색은 2번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.

 

[RGB2]
1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.

 

추가된 조건을 정리해보면 다음과 같다.

 

N번의 집과 1번 집이 서로 영향을 미친다!

 

처음에 이 조건을 보고 원형적으로 생각해서 풀어야 되나.. 생각했는데 지금 생각해보니 말도 안 되는 멍멍이 소리였고..

 

곰곰이 생각해보았다

 

음... 삼중 dp를 사용해야 하나? 그건 너무 귀찮은데 

그럼 첫 번째 집을 연산할 때 마지막 집까지 연산해 버릴까? 그건 또 이상한데..

 

그럼 첫 번째 집을 고정시켜 버릴까??

 

음..

????!!!!!!!!!!!!!!! 

이 방법 괜찮은 것 같은데? 

 

여기까지 내 의식의 흐름이었고 이렇게 문제를 풀었다.

 

결국 해결방안은 위의 생각이었다.

 

첫 번째 집을 고정시킨다.

즉 마지막 집은 반드시 첫 번째 집의 색깔에 의해 결정되기 때문에 첫 번째 집을 고정시켜 버리면 

빠밤!

 

이렇게 생각하고 코드를 짜다 보니 문제가 생겼다. (아마 나와 같이 생각한 사람들은 대부분 겪었을 텐데)

 

예를 들어 보이면 (문제의 예제 1번)

 

ex) 첫 번째 집의 색깔을 RED로 고정한 경우

 

첫 번째 집 :   26  

두 번째 집 :    0    86   83

 

즉 첫 번째 집을 RED로 고정한 경우에는 두 번째 집은 RED를 선택하지 못하므로 dp값이 0이 된다.

 

뭐 당연한 얘기지만 그래 그렇다고 하자고

 

근데 문제는 세 번째 집에서 나타난다.

 

첫 번째 집 :   26 

두 번째 집 :    0    86   83

세 번째 집 :   96   89   99

 

..? 

 

이렇게 보니까 잘 안보이넼ㅋㅋㅋㅋㅋㅋ

 

그럼 다시 살짝? 바꿔보면

 

첫 번째 집 :   26 

두 번째 집 :            0                    86                   83

세 번째 집 :   83 + cost [3][0]     0 + cost [3][1]    0 + cost [3][2]

 

이제는 보인다

 

세 번째 집의 BLUE와 GREEN은 무조건 두 번째 집의 RED를 선택하게 된다는 것이다.

 

그러면 안되는데..

 

이런 문제점 때문에 나는 저 0 부분을 쓰레기 값으로 초기화시켜놓고 계산했다.

 

마지막으로 N번째 집에서는 첫 번째 집의 색깔을 고르면 안되기 때문에 그 부분에 대해서 생각하고 코드를 짜면 된다.

 

이렇게 첫 번째 집을 고정시키는 for문 하나와 나머지 dp배열을 채우는 for문으로

이중 for문으로 구할 수 있었다.

(시간 복잡도도 여유롭겠죠?)

 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
 
int dp[1004][3];
int cost[1004][3];
int n;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> cost[i][j];
        }
    }
    int ans = 2000000000;
    for (int k = 0; k < 3; k++) { // k(0 = red, 1 = green, 2 = blue) 색깔로 고정!
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i < n; i++) {
            if (i == 1) { // 두 번째 집부터 시작, 예외처리
                for (int j = 0; j < 3; j++) {
                    if (j == k) {
                        // 이 곳을 뽑을 수 없게 만들어야 함.
                        dp[i][j] = 2000000000; // 쓰레기값
                        continue;
                    }
                    dp[i][j] = cost[0][k] + cost[i][j];
                }
                continue;
            }// 기존 RGB 구하는 코드
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];
        }
        for (int i = 0; i < 3; i++) {
            if (i == k) continue; // 마지막 집은 첫 번째 집의 색깔을 계산하지 않는다
            ans = min(dp[n - 1][i], ans);
        }
    }
    if (n == 1) ans = min(cost[0][1], min(cost[0][0], cost[0][1])); // n = 1일때 예외처리
    cout << ans << "\n";
}

 

아니 남들보다 더 쉽게 풀어써보려고 했는데 뭔가 더 어렵게 쓴 거 같넹..

 

생각보다 까다로운? 문제였다ㅎㅎ