[백준/C++] 1149번 RGB거리

백준

 

---

🤔문제 이해

같은 색이 연속으로 나오지 않게 칠했을 때 비용이 가장 적게 드는 경우의 비용을 구하는 문제이다.

---

🔥풀이🔥

전에 풀어본게 기억이 나서 바로 DP를 이용해 풀었다.

dp[i][j]에서 i는 집의 번호, j는 색을 의미한다.

dp[i][0]은 0을 칠했을 때 그 전 집에서 칠할 수 있는 경우는 1과 2이므로 dp[i-1][1]과 dp[i-1][2]를 비교해 더 작은 값과 i번째 집을 0으로 칠했을 때의 비용과 합해 dp[i][0]을 업데이트 해준다.

색깔 1과 2도 동일하게 해주게 되면 마지막 집에서 색을 0을 칠했을 때 vs 1을 칠했을 때 vs 2를 칠했을 때를 비교해 그 최솟값을 출력해준다.

---

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<vector<int>> dp;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n;
    dp.resize(n + 2);
    int x;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> x;
            dp[i].push_back(x);
        }
    }

    for (int i = 2; i <= n; i++) {
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + dp[i][0];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + dp[i][1];
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + dp[i][2];
    }
    int min_cost = dp[n][0];
    for (int i = 1; i < 3; i++) {
        if (min_cost > dp[n][i]) min_cost = dp[n][i];
    }
    cout << min_cost;
}