백준 17404번 RGB거리 2

🔒[문제 url]

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

🔑알고리즘

색의 제약없이 $1$번 집과 $N$번 집이 칠해지는 경우의 수는 다음과같다.
1. $1$번 집 : 빨 $N$번 집 : 빨
2. $1$번 집 : 빨 $N$번 집 : 초
3. $1$번 집 : 빨 $N$번 집 : 파
4. $1$번 집 : 초 $N$번 집 : 빨
5. $1$번 집 : 초 $N$번 집 : 초
6. $1$번 집 : 초 $N$번 집 : 파
7. $1$번 집 : 파 $N$번 집 : 빨
8. $1$번 집 : 파 $N$번 집 : 초
9. $1$번 집 : 파 $N$번 집 : 파

$1$번 집을 칠할 색을 바꿔가며, N번 집의 색과 같은 경우를 제외한 값 중 최솟값을 찾으면 된다.

• 빨강을 0 초록을 1 파랑을 2 로 지정하고,
  dp[x][y] : $y$번 집을 $x$초 칠했을 때의 최솟값으로 선언한다.
  이후 과정은 다음과 같다.
  • dp[0][i] : min(dp[1][i-1],dp[2][i-1])
  • dp[1][i] : min(dp[0][i-1],dp[2][i-1])
  • dp[2][i] : min(dp[0][i-1],dp[1][i-1])

🐾부분 코드

// Init
dp[0][1] = 2e9; dp[1][1] = 2e9; dp[2][1] = 2e9;
if(rgb == 0) dp[0][1] = R[1];
else if(rgb == 1) dp[1][1] = G[1];
else dp[2][1] = B[1];

<dp 배열 초기화>
rgb는 1번 집을 칠할 색깔을 의미한다.
dp[rgb][1]이외의 dp[][1]을 매우 큰 값으로 지정하여,
1번 집을 다른 색으로 칠하지 않도록 한다.

//DP
for (int i = 2; i <= n; i++)
{
    dp[0][i] = R[i] + min(dp[1][i - 1], dp[2][i - 1]);
    dp[1][i] = G[i] + min(dp[0][i - 1], dp[2][i - 1]);
    dp[2][i] = B[i] + min(dp[0][i - 1], dp[1][i - 1]);
}

<dp 배열 갱신>
이전 집과 색이 같지 않도록 dp 배열을 갱신한다.

// 최솟값 갱신
for(int i = 0; i < 3; i++)
{
    // 처음 집과 마지막 집의 색이 같다면 고려하지 않는다.
    if(i == rgb) continue;
    ans = min(ans,dp[i][n]);
}

<1번과 N번 집의 색 동일 방지>
마지막 집이 rgb로 칠해진 집은 고려하지 않는다.

🪄전체 코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int n;
int R[1001];
int G[1001];
int B[1001];
int dp[3][1001];

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> R[i] >> G[i] >> B[i];
}


void SOLVE()
{

    int ans = 2e9;
    for(int rgb = 0; rgb < 3; rgb++)
    {// rgb : 1번 집의 색

        // Init
        dp[0][1] = 2e9; dp[1][1] = 2e9; dp[2][1] = 2e9;
        if(rgb == 0) dp[0][1] = R[1];
        else if(rgb == 1) dp[1][1] = G[1];
        else dp[2][1] = B[1];
        
        // DP
        for (int i = 2; i <= n; i++)
        {
            dp[0][i] = R[i] + min(dp[1][i - 1], dp[2][i - 1]);
            dp[1][i] = G[i] + min(dp[0][i - 1], dp[2][i - 1]);
            dp[2][i] = B[i] + min(dp[0][i - 1], dp[1][i - 1]);
        }

        // 최솟값 갱신
        for(int i = 0; i < 3; i++)
        {
            // 처음 집과 마지막 집의 색이 같다면 고려하지 않는다.
            if(i == rgb) continue;
            ans = min(ans,dp[i][n]);
        }
    }

    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

RGB 1에서 한 가지 조건만 추가되었는데 구현 난이도가 많이 올라갔다고 느껴졌다. 일주일동안 DP만 했는데 여전히 DP는 어렵군요!😫