[BOJ]17404번: RGB거리 2(c++)

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

17404번: RGB거리 2

 

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    // 입력
    const int MAX = 1000;
    int rgb[MAX + 1][3];
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> rgb[i][0] >> rgb[i][1] >> rgb[i][2];
    }
    
    /*
    점화식
        D[i] : i 번째 집까지 색칠한 최소 비용.
        D[i] = i 번째 집 색칠 비용 + (i - 1)번째 집까지 색칠한 최소 비용
 
        i번째 집은 (i - 1)번째 집과 색이 같으면 안되므로
        --> D[i][k] = rgb[i][k] + min(D[i - 1][(k + 1) % 3, D[i - 1][(k + 2) % d]]) (0 <= k <= 2)
    
 
        추가조건) 1번째 집은 N번째 집과 색이 같으면 안된다.
        1번째 집이 R일때, G일때, B일때를 각각 구해서 최소비용 구하기
        
        * 주의사항 *
        a. 1번째 집의 색깔이 X일때, D[1]과 D[2]는 이미 정해져 있다
        b. 1번째 집의 색깔이 X일때, N번째 집의 색깔은 X이면 안된다.
    */
    int min_cost = MAX * MAX;
    for (int k = 0; k < 3; k++)
    {
        int cost[MAX + 1][3] = { 0, };
 
        // 주의사항 a 처리
        for (int i = 0; i < 3; i++)
        {
            if (i == k)
            {
                cost[1][i] = rgb[1][i];
                continue;
            }
            cost[1][i] = 1000;
        }
 
        // 점화식 구현
        for (int i = 2; i <= N; i++)
        {
            cost[i][0] = rgb[i][0] + min(cost[i - 1][1], cost[i - 1][2]);
            cost[i][1] = rgb[i][1] + min(cost[i - 1][0], cost[i - 1][2]);
            cost[i][2] = rgb[i][2] + min(cost[i - 1][0], cost[i - 1][1]);
        }
 
        // 주의사항 b처리
        for (int i = 0; i < 3; i++)
        {
            if (i == k)
            {
                continue;
            }
            min_cost = min(min_cost, cost[N][i]);
        }
    }
 
    cout << min_cost;
 
    return 0;
}

 

 

TIP

주어진 범위를 잘 생각하며 구현하자.

 

 

다음은 처음에 시도했다가 망한 코드이다.

int min_cost = MAX * MAX;
for (int k = 0; k < 3; k++)
{
    int cost[MAX + 1][3] = {0,};
    
    // 주의사항 a처리하려고 했는데 망함! 이유는?
    for (int i = 1; i <= N; i++)
    {
        if (i == 2)
        {
            cost[i][k] = 1000;
            cost[i][(k + 1) % 3] = rgb[i][(k + 1) % 3] + cost[1][k];
            cost[i][(k + 2) % 3] = rgb[i][(k + 2) % 3] + cost[1][k];
            continue;
        }
 
        cost[i][0] = rgb[i][0] + min(cost[i - 1][1], cost[i - 1][2]);
        cost[i][1] = rgb[i][1] + min(cost[i - 1][0], cost[i - 1][2]);
        cost[i][2] = rgb[i][2] + min(cost[i - 1][0], cost[i - 1][1]);
 
    }
    // 주의사항 b처리
    for (int i = 0; i < 3; i++)
    {
        if (i == k)
        {
            continue;
        }
        min_cost = min(min_cost, cost[N][i]);
    }
}

 

예제 값 넣었을땐 잘 돌아갔는데 제출하니 바로 틀린답이라고 떴다. 

이유가 뭘까?

애초에 나는 왜 D[2][X]를 1000으로 두려고 했을까?

 

1번째 집 색깔이 X일때, 3번째 집 cost를 구할때

D[2]의 최소비용에서 D[2][X] 경우를 제외하고 싶어서! 였다.

 

BUT!

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다.

문제에서는 위처럼 N이 2이상이라고 주어져 있다. 

이때 cost[2]의 값을 내가 임의로 조작하는게 올바를까? 

-->NO. 그래서 틀린 것이다.

 

1번째 집 색깔이 X일때, D[2]에서 D[2][X]의 경우를 제외하고 싶다면

D[1][X] 의 값을 MAX로 조정하는게 옳다.

 

문제에서 D[1]을 물어볼 일은 없을테니까