[백준] 17404_RGB거리 2 C++

02 Jul 2023 in Study on Coding Test

DP를 활용해보는 문제

정답제출코드

#include <iostream>

#define MAX 1001
#define INF 1000000000

using namespace std;

int N;
int Color[MAX][3];

int m_min(int a, int b)
{
    if (a < b)
        return a;
    else
        return b;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    for (int i = 1; i <= N; ++i)
    {
        int r, g, b;
        cin >> r >> g >> b;

        Color[i][0] = r;
        Color[i][1] = g;
        Color[i][2] = b;
    }
        

    int result = INF;

    for (int i = 0; i <= 2; ++i)
    {
        int dp[MAX][3];

        for (int j = 0; j <= 2; ++j)
        {
            if(j == i)
                dp[1][i] = Color[1][i];
            else
                dp[1][j] = INF;
        }

        for(int j = 2; j <= N; ++j)
        {
            dp[j][0] = m_min(dp[j-1][1], dp[j-1][2]) + Color[j][0];
            dp[j][1] = m_min(dp[j-1][0], dp[j-1][2]) + Color[j][1];
            dp[j][2] = m_min(dp[j-1][1], dp[j-1][0]) + Color[j][2];
        }

        for(int j = 0; j <= 2; ++j)
        {
            if(j == i)
                continue;
            result = m_min(result, dp[N][j]);
        }
    }

    cout << result;

    return 0;
}

백준 1149번에서 조건이 추가된 문제이다.

조건은 처음 집과 마지막 집이 색깔이 달라야 한다는 것이다.

이 조건을 달성하기 위해서 9가지의 경우를 검사하고 3가지 경우를 빼야할 것이다.

• 1번집이 R이고 마지막집이 R일때 최소비용
• 1번집이 R이고 마지막집이 G일때 최소비용
• 1번집이 R이고 마지막집이 B일때 최소비용
• 1번집이 G이고 마지막집이 R일때 최소비용
• 1번집이 G이고 마지막집이 G일때 최소비용
• 1번집이 G이고 마지막집이 B일때 최소비용
• 1번집이 B이고 마지막집이 R일때 최소비용
• 1번집이 B이고 마지막집이 G일때 최소비용
• 1번집이 B이고 마지막집이 B일때 최소비용

즉, 2중 for문을 만들 뒤 외부에서는 3번, 내부에서는 for문을 3개 돌리는 형식으로 취하고,

1번, 5번, 9번 경우를 제외시키기 위해서 코드를 아래와 같이 짜준다.

for(int j = 0; j <= 2; ++j)
{
    if(j == i) // 처음 집과 마지막 집의 색깔이 같을 경우 제외
        continue;
    result = m_min(result, dp[N][j]);
}

이렇게해서 result를 추출하면 끝.