백준 17404 - RGB거리 2

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

17404번: RGB거리 2

RGB거리 1번 문제에서 하나의 조건 (첫 번째 집과 마지막 집의 색깔도 달라야 한다) 이 추가된 버전. 이것때문에 조금 헤맸다.

 

먼저 이 조건을 무시한 채 dp 풀이를 적용해보자.

 

1) dp식 정의

dp[i][j] (0 <= j <= 2) : i번째 집을 빨강 0, 초록 1, 파랑 2의 색깔로 칠했을 때의 전체 비용의 최솟값

 

2) 초깃값

첫 번째 집은 어느 색도 앞 집과 겹치지 않기 때문에 모든 색을 칠할 수 있다.

dp[1][j] = cost[1][j], cost[i][j]는 i번째 집 하나를 j번 색깔로 칠하는 단일 비용

 

3) 점화식

두 번째 집부터는 앞 집과 색깔이 겹치면 안 된다. 따라서 현재 집을 특정 색깔로 칠하는 전체 비용은 앞 집을 나머지 두 색깔로 칠했을 때의 비용에서 계산해야 한다. 예를 들어 dp[2][1]을 구하고자 하면 dp[1][0], dp[1][2] 중 더 적합한 값을 골라 거기에 현재 집을 칠하는 비용 cost[2][1]을 더하면 된다. 문제에서 최솟값을 구하라고 했으므로 dp[1][0], dp[1][2] 중 더 작은 값을 선택하면 된다.

 

리빙포인트) 모듈러 연산을 활용하면 반복문을 훨씬 더 짧고 명확하게 나타낼 수 있다.

j가 0일때 1, 2번 색을 / j가 1일때 0, 2번 색을 / j가 2일때 0, 1번 색을 확인하면 된다.

 

아래의 표를 보자.

j	( j + 1 ) % 3	( j + 2 ) % 3
0	1	2
1	2	0
2	0	1

짜잔~ 모듈러 연산을 통해 0~2 사이 값에 대해 나머지 두 수를 찾을 수 있다.

 

이를 적용한 코드는 다음과 같다.

    for (int i = 2; i <= size; i++) {
        for (int j = 0; j < 3; j++) {

            //모듈러 연산을 이용해 다른 두 색깔의 최솟값을 구한다.
            int idx1 = (j + 1) % 3, idx2 = (j + 2) % 3;
            int minIdx = dp[i - 1][idx1] < dp[i - 1][idx2] ? idx1 : idx2;

            dp[i][j] = dp[i - 1][minIdx] + cost[i - 1][j];
        }
    }

 

마지막으로 맨 처음에 말했던 조건 (첫 번째 집과 마지막 집의 색깔도 달라야 한다)을 추가해보자.

 

첫 번째 집의 색깔을 비용이 가장 낮은 색깔이 아닌 내가 선택한 임의의 색으로 설정한다. 예를 들어 첫 집을 빨간색으로 설정하고 싶으면, dp[2][2]와 dp[2][3]에서 dp[1][2]나 dp[1][3]이 아닌 dp[1][1]을 선택하도록 자신만의 방법으로 처리하면 된다. 그리고 dp배열을 모두 채우고 나면, dp[N][1]은 첫 집과 마지막 집의 색깔이 같은 경우이므로 최솟값 계산에서 제외한다. 그러면 가능한 최솟값은 dp[N][2]나 dp[N][3]이 될 것이다.

 

이 과정을 R G B 3가지 색에 대해 모두 수행해보면서 3개의 경우중 가장 낮은 최솟값을 찾아 출력하면 된다.

리빙포인트2) min 함수에서 두 개가 아닌 여러 개 중 최솟값을 찾고자하면, 그 값들을 { }로 묶으면 된다.

ret = min({ret, dp[N][0], dp[N][1] , dp[N][2] });