Boj 1149 c++ RGB거리

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

 

- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.

- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.

- i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.                                 

 

이차원 dp로 풀이하였다. 전 배열까지의 최소비용의 상태에 따라 현재 상태를 정해준다.

#include<iostream>
using namespace std;
int dp[1001][4];//i번째 번지수에서 j 색깔을 골랐을 때의 최소비용
int cost[1001][4];
void init(){
ios_base :: sync_with_stdio(0);
cin.tie(0);
}
int main(){
    init();
    int N;
    cin>>N;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=3; j++){
            cin>>cost[i][j];
            if(j==1){
                dp[i][j]=cost[i][j]+min(dp[i-1][j+1], dp[i-1][j+2]);
            } else if (j==2) {
                dp[i][j]=cost[i][j]+min(dp[i-1][j-1], dp[i-1][j+1]);
            } else {
                dp[i][j]=cost[i][j]+min(dp[i-1][j-1], dp[i-1][j-2]);
            }
        }
    } cout<<min(min(dp[N][1], dp[N][2]), dp[N][3]);
}