[백준] 17404번 : RGB거리 2

문제

 

---

풀이

 

myunji.tistory.com/208

[백준] 1149번 : RGB거리

이 문제의 응용 버전이다. 선형으로 배치됐던 집이 이젠 원형으로 배치된다.

 

고등학교 시절 원순열을 배울 때 선생님이 이런 말씀을 하셨다.

"원순열은 시작점이 없어서 헷갈리니까 일단 한 놈을 죽여서 앉힌다고 생각해"

물론 죽인다 식의 표현은 격한 면이 있지만 덕분에 이렇게 몇년이 지난 지금도 잊지 않고 있다.

 

이 문제의 접근도 똑같이 하면 된다.

일단 첫번째 집의 색을 고정하고 집들을 색칠해 나가면 된다.

 

첫번째 집의 색정보가 있으니 마지막 집과 겹치지 않게 할 수 있다.

---

소스코드

 

#include <iostream>
#include <algorithm>

using namespace std;

const int INF = 1000000000;
int cost[1000][3], N;

int dpPaint(int first) {
    int dp[1000][3];

    for (int i = 0; i < 3; i++) {
        if (i == first) //첫번째 집과 두번째 집을 같은 색으로 칠할 수 없음
            dp[1][i] = INF;
        else //첫번째 집의 색으로 칠함
            dp[1][i] = cost[1][i] + cost[0][first];
    }
    for (int i = 2; i < N; i++) { //최소비용
        dp[i][0] = cost[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
        dp[i][1] = cost[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
        dp[i][2] = cost[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
    }
    int result = INF;
    for (int i = 0; i < 3; i++) { //첫번째 집과 마지막 집의 색이 같은 경우를 제외하고 최소 비용 갱신
        if (i != first)
            result = min(result, dp[N - 1][i]);
    }
    return result;
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 3; j++)
            cin >> cost[i][j];
    }
    int min_cost = INF;
    for (int i = 0; i < 3; i++) //첫번째 집의 색을 바꾸면서 최소 비용 갱신
        min_cost = min(min_cost, dpPaint(i));
    cout << min_cost;
}

전체 소스코드다.

 

int dpPaint(int first) {
    int dp[1000][3];

    for (int i = 0; i < 3; i++) {
        if (i == first) //첫번째 집과 두번째 집을 같은 색으로 칠할 수 없음
            dp[1][i] = INF;
        else //첫번째 집의 색으로 칠함
            dp[1][i] = cost[1][i] + cost[0][first];
    }
    for (int i = 2; i < N; i++) { //최소비용
        dp[i][0] = cost[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
        dp[i][1] = cost[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
        dp[i][2] = cost[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
    }
    int result = INF;
    for (int i = 0; i < 3; i++) { //첫번째 집과 마지막 집의 색이 같은 경우를 제외하고 최소 비용 갱신
        if (i != first)
            result = min(result, dp[N - 1][i]);
    }
    return result;
}

색을 칠하는 dpPaint 함수이다.

first로 들어오는 값은 0~2인데 이 값에 따라 두 번째 집의 dp를 설정한다.

 

일단 dp[1][first]는 칠할 수 없다. 첫 번째 집과 두 번째 집의 색이 겹치게 되기 때문이다.

나머지 dp[1][j]는 첫번째 집의 이번 색인 cost[0][first]로 칠한다.

 

그리고 세 번째 집부터 1149번을 풀었을 때처럼 집을 색칠한다.

 

마지막에 최소비용을 리턴하는데 dp[N-1][first]인 경우는 빼야한다.

첫번째 집과 마지막 집의 색이 같아지기 때문이다.

 

    int min_cost = INF;
    for (int i = 0; i < 3; i++) //첫번째 집의 색을 바꾸면서 최소 비용 갱신
        min_cost = min(min_cost, dpPaint(i));
    cout << min_cost;

main에서 이렇게 첫번째 집의 색을 바꾸면서 최종 비용을 갱신해 나간다.