[백준] 1149 RGB 거리 DP

ㅇ문제 :

www.acmicpc.net/problem/1149

1149번: RGB거리

 

분석 :

rgb 색깔을 양 옆 집마다 겹치지 않게 색칠하는데 그 최소 비용을 구하는 문제다.

dp 배열은 2차원 배열로 이루어져 있으며 dp[i][0], dp[i][1], dp[i][2]는 각각 i번째 집까지 색칠할때 0-빨간색 최소 비용,1-노란색 최소 비용,2-파란색 최소 비용을 저장하고 있는 배열이다.

예를 들어 dp[1][1]은 이전 0번째 집을 색칠할때 드는 최소 비용에 지금 자신의 1번째 집을 노란색으로 색칠하는 것까지 계산된 비용을 의미한다.

따라서 우리는 dp의 마지막 줄(N)의 최소값을 구하면 1 ~ N까지 색칠하는데 드는 최소 비용을 구할 수 있다.

 

c++ 코드 :

//
//  1149_rgb.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/04/23.
//

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>

using namespace std;
int arr[1001][3]; // rgb3
int dp[1001][3];
int N;

void make_rgb_paint(){
    dp[0][0] = arr[0][0];
    dp[0][1] = arr[0][1];
    dp[0][2] = arr[0][2];
    
    for(int i = 1; i < N; i++){
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0];
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1];
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + arr[i][2];
    }
    
    int ans = min(min(dp[N-1][0],dp[N-1][1]),dp[N-1][2]);
    cout << ans << '\n';
    
}

int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        for(int j = 0; j< 3; j++){
            cin >> arr[i][j];
        }
    }
    
    make_rgb_paint();
    return 0;
}