[백준] 1149번 RGB거리

문제 주소

백준 1149번 RGB거리

1149번: RGB거리

알고리즘

DP

 

힌트

배열에 각 집에서 각각의 색을 칠하는데 최소 비용을 저장한다.

 

문제 풀이

dp배열은 그 집에서 각 색을 칠할때의 최소 비용을 저장하는 배열이다. RGB를 각각 012원소에 넣고 i번째 집에서 0번째 색을 칠하기 위한 최소 비용은 i-1번째 집에서 1 또는 2를 칠하기 위한 최소 비용중 작은 값에 cost[i][0]을 더한 값이다.

#include<iostream>
using namespace std;

int cost[1000][3];
int dp[1000][3];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>cost[i][0]>>cost[i][1]>>cost[i][2];
    }

    dp[0][0]=cost[0][0];
    dp[0][1]=cost[0][1];
    dp[0][2]=cost[0][2];

    for(int i=1;i<n;i++){
        for(int j=0;j<3;j++){
            dp[i][j]=min(dp[i-1][(j+1)%3],dp[i-1][(j+2)%3])+cost[i][j];
        }
    }    

    cout<<min(min(dp[n-1][1],dp[n-1][0]),dp[n-1][2]);
}

백준 1149번 RGB거리