백준 1149 (RGB 거리) C++

문제

1149번: RGB거리

집에 빨간색이나 초록, 파란색으로 칠할 수 있는데 서로 붙어 있는 집은 같은 색을 칠하면 안됩니다.

 

먼저 각각 집에 대해서 가격을 저장해야 합니다.

1 = 빨간, 2 = 초록, 3 = 파랑

price[n][1] = n번째 집을 빨간으로 칠하는데 드는 비용입니다.

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 3; j++) {
            int color;
            cin >> color;
            price[i][j] = color;
        }
    }

 

이제 점화식을 세우겠습니다. 

우리는 총 3가지의 경우의 수를 세울 수 있습니다. 처음에 집의 색을 선택하는 경우가 3가지 이기 때문입니다.

따라서 base case는 dp[1][1] = price[1][1], dp[1][2] = price[1][2], dp[1][3] = price[1][3]으로 해줍니다.

dp[n][1]은 n번째 집을 빨간색으로 칠하는데 지금까지 조건에 맞게 칠했을때 비용의 총합을 저장합니다.

따라서 dp[n][1] = price[n][1] + min(dp[n-1][2], dp[n-1][3]) 으로 점화식을 세울 수 있습니다.

dp[1][1] = price[1][1];
    dp[1][2] = price[1][2];
    dp[1][3] = price[1][3];
    for (int i = 2; i <= n; i++) {
        dp[i][1] += price[i][1] + min(dp[i - 1][2], dp[i - 1][3]);
        dp[i][2] += price[i][2] + min(dp[i - 1][1], dp[i - 1][3]);
        dp[i][3] += price[i][3] + min(dp[i - 1][1], dp[i - 1][2]);
    }

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int price[1001][4];
int dp[1001][1001];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 3; j++) {
            int color;
            cin >> color;
            price[i][j] = color;
        }
    }
    dp[1][1] = price[1][1];
    dp[1][2] = price[1][2];
    dp[1][3] = price[1][3];
    for (int i = 2; i <= n; i++) {
        dp[i][1] += price[i][1] + min(dp[i - 1][2], dp[i - 1][3]);
        dp[i][2] += price[i][2] + min(dp[i - 1][1], dp[i - 1][3]);
        dp[i][3] += price[i][3] + min(dp[i - 1][1], dp[i - 1][2]);
    }
    cout << min(min(dp[n][1], dp[n][2]), dp[n][3]);
 
 
    return 0;
}