1149번 - RGB거리

📌문제

👉 문제보기

코드

#include <iostream>
#include <vector>
#define MIN(x, y) (x < y ? x : y)

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<vector<int>> vec(n);
    vector<vector<int>> dp(n);

    for (int i = 0; i < n ; i++) {
        for (int j = 0; j < 3; j++) {
            int x;
            cin >> x;
            vec[i].push_back(x);
            dp[i].push_back(x);
        }
    }

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

    cout << min << '\n';



    return 0;
}

🍳문제 풀이

RGB 각각의 위치를 0, 1, 2번째 열이라고 봤을 때, dp[i][0]은 RGB를 담은 배열의 vec[i][0]과 dp[i][1] 혹은 dp[i][2] 중에 작은 것의 합을 넣으면 된다.
dp[n - 1]번째까지 반복해서 돌고 마지막 dp행의 값 중 가장 작은 값을 출력하면 최소값을 얻을 수 있다.