백준 1149번, RGB거리

백준 1149번 c++ 문제풀이

문제:

백준 1149

풀이:

1. 다이나믹 프로그래밍으로 접근한다.
2. 먼저 첫번째 집을 빨강, 초록, 파랑으로 칠했을 때의 값들을 저장한다.(각각의 색으로 칠했을 때의 최솟값을 저장하는데, 첫번째 선택이기 때문)
3. 두번째 집부터는 현재 색칠하는 색의 가격과 이전 집에 저장된 최솟값들 중 조건에 맞는 색중에서 더 작은 값을 더해준다.
4. 예를 들어 현재 집을 빨강으로 칠하면 이전 집이 파랑일 때의 최솟값과 초록일 때의 최솟값을 비교하여 더 작은 값을 더해 저장하는 것이다.
5. 마지막 집까지 오면 마지막 집을 빨강, 파랑, 초록으로 칠했을 때의 최솟값들이 나오는데, 그 중 제일 작은 값이 모든 집을 최솟값으로 칠하는 비용이다.

코드:

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n;

void dp(vector<int> v[]){
    
    int dp[n][3]; //i 번째 집을 빨간색, 파란색, 초록색으로 칠할 때 드는 최소비용

    dp[0][0] = v[0][0]; //빨강
    dp[0][1] = v[0][1]; //초록
    dp[0][2] = v[0][2]; //파랑
    //첫번째 집을 각각의 색으로 칠할 때 드는 최소비용
    for(int i=1;i<n;i++){
        for(int j=0;j<3;j++){
            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + v[i][0];
            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + v[i][1];
            dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + v[i][2];
        }
    }

    int min_v = min(min(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);

    cout << min_v;
}

int main(){

    cin >> n;

    vector<int> v[n];

    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            int price;

            cin >> price;

            v[i].push_back(price);
        }
    }
    
    dp(v);
    return 0;
}

감사합니다.