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

 

 

풀이

• dp배열 초기화한다. 
• 2번 집부터 N번 집까지 순서대로 각 집을 빨강, 초록, 파랑으로 칠하는데 드는 최솟값을 계산하여 DP 배열에 저장한다.
• 각 집을 칠할 때, 이전 집과 색이 겹치지 않도록 하며 최솟값을 선택한다.
• 모든 집을 칠하는 비용의 최솟값은 DP 배열의 마지막 행에서 가장 작은 값이다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<vector<int>> cost(N, vector<int>(3));
    for (int i = 0; i < N; ++i) {
        cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
    }

    vector<vector<int>> dp(N, vector<int>(3));

    // 초기값 설정
    dp[0][0] = cost[0][0];
    dp[0][1] = cost[0][1];
    dp[0][2] = cost[0][2];

    // Dynamic Programming을 통해 최솟값 계산
    for (int i = 1; i < N; ++i) {
        dp[i][0] = cost[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
        dp[i][1] = cost[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
        dp[i][2] = cost[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
    }

    // 모든 집을 칠하는 비용의 최솟값 출력
    cout << min(min(dp[N - 1][0], dp[N - 1][1]), dp[N - 1][2]) << endl;

    return 0;
}

 

 

 

 

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

1149번: RGB거리