[백준 BOJ] 17404번 - RGB거리 2(C++)

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

17404번: RGB거리 2

DP를 이용하면 쉽게 풀 수 있는 문제이다. 2차원 배열 dp[N][3]로 만들고 for문을 3~N까지 돌면서 해당 level의 집에서 1~3번째의 색으로 칠할 때 해당 번째의 수를 뺀 전의 값 두 개 중에서 min값을 찾아서 더해주면 된다. 즉, dp[i][2]이면 min(dp[i-1][1],dp[i-3])+arr[i][2] 해주면 된다. 이 때 arr[i][2]는 i번째 집을 색칠할 때 드는 비용 중 두 번째의 있는 값이다. 획기적인 생각이 안 떠올라서 첫 번째 집과 두 번째 집의 색을 미리 정해놓고 for문을 돌리는 식으로 만들어서 코드가 길게 되었다.

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <vector>

#define endl '\n'
#define ll long long
#define pii pair<int, int>
#define max 987654321

using namespace std;

int N;
int arr[1001][4];
int dp[1001][4];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= 3; j++)
        {
            cin >> arr[i][j];
        }
    }
    dp[1][1] = arr[1][1];
    dp[2][2] = dp[1][1] + arr[2][2];
    dp[2][3] = dp[1][1] + arr[2][3];
    dp[2][1] = max;
    for (int i = 3; i <= N; i++)
    {
        for (int j = 1; j <= 3; j++)
        {
            if (i == N)
            {
                if (j == 3)
                    dp[i][j] = arr[i][j] + min(dp[i - 1][1], dp[i - 1][2]);
                else if (j == 2)
                    dp[i][j] = arr[i][j] + min(dp[i - 1][1], dp[i - 1][3]);
                else if(j==1)
                    dp[i][j]=max;
            }
            else
            {
                if (j == 3)
                    dp[i][j] = arr[i][j] + min(dp[i - 1][1], dp[i - 1][2]);
                else if (j == 2)
                    dp[i][j] = arr[i][j] + min(dp[i - 1][1], dp[i - 1][3]);
                else if (j == 1)
                    dp[i][j] = arr[i][j] + min(dp[i - 1][2], dp[i - 1][3]);
            }
        }
    }
    int minNum = max;
    for (int i = 1; i <= 3; i++)
    {
        if (minNum > dp[N][i])
            minNum = dp[N][i];
    }
    memset(dp, 0, sizeof(dp));
    dp[1][2] = arr[1][2];
    dp[2][1] = dp[1][2] + arr[2][1];
    dp[2][3] = dp[1][2] + arr[2][3];
    dp[2][2] = max;
    for (int i = 3; i <= N; i++)
    {
        for (int j = 1; j <= 3; j++)
        {
            if (i == N)
            {
                if (j == 3)
                    dp[i][j] = arr[i][j] + min(dp[i - 1][1], dp[i - 1][2]);
                else if (j == 1)
                    dp[i][j] = arr[i][j] + min(dp[i - 1][2], dp[i - 1][3]);
                else if(j==2)
                    dp[i][j]=max;
            }
            else
            {
                if (j == 3)
                    dp[i][j] = arr[i][j] + min(dp[i - 1][1], dp[i - 1][2]);
                else if (j == 2)
                    dp[i][j] = arr[i][j] + min(dp[i - 1][1], dp[i - 1][3]);
                else if (j == 1)
                    dp[i][j] = arr[i][j] + min(dp[i - 1][2], dp[i - 1][3]);
            }
        }
    }
    for (int i = 1; i <= 3; i++)
    {
        if (minNum > dp[N][i])
            minNum = dp[N][i];
    }
    memset(dp, 0, sizeof(dp));
    dp[1][3] = arr[1][3];
    dp[2][2] = dp[1][3] + arr[2][2];
    dp[2][1] = dp[1][3] + arr[2][1];
    dp[2][3] = max;
    for (int i = 3; i <= N; i++)
    {
        for (int j = 1; j <= 3; j++)
        {
            if (i == N)
            {
                if (j == 1)
                    dp[i][j] = arr[i][j] + min(dp[i - 1][2], dp[i - 1][3]);
                else if (j == 2)
                    dp[i][j] = arr[i][j] + min(dp[i - 1][1], dp[i - 1][3]);
                else if(j==3)
                    dp[i][j]=max;
            }
            else
            {
                if (j == 3)
                    dp[i][j] = arr[i][j] + min(dp[i - 1][1], dp[i - 1][2]);
                else if (j == 2)
                    dp[i][j] = arr[i][j] + min(dp[i - 1][1], dp[i - 1][3]);
                else if (j == 1)
                    dp[i][j] = arr[i][j] + min(dp[i - 1][2], dp[i - 1][3]);
            }
        }
    }
    for (int i = 1; i <= 3; i++)
    {
        if (minNum > dp[N][i])
            minNum = dp[N][i];
    }
    cout << minNum;
    return 0;
}