백준 9095번 :R G B 거리

문제 링크 :https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

 

 문제 설명 

 

집의 갯수가 주어지고 각집마다 빨강,초록,파랑 으로 색칠할때 드는 비용이 주어진다

각집은 옆집과 똑같은 색으로 칠할 수 없다 이때 모든집을 칠할수 있는 총 비용의 최소값 출력 .

 

 알고리즘 

 

DP배열을 2차원으로 설정한다 .

DP[집순서][색] // 0:빨강 1:초록 2:파랑

각집을 빨,초,파 로색칠했을 때의 최소비용을 점화식을 이용하여 업데이트 시켜주면 된다.

 

점화식 : DP[i][0]=MIN(DP[i-1][1],DP[i-1][2])

           DP[i][1]=MIN(DP[i-1][0],DP[i-1][2])

           DP[i][2]=MIN(DP[i-1][0],DP[i-1][1])

 

코드 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
 
int main() {
    int N;
    cin >> N;
    int dp[1003][3];
 
 
    int arr[1005][3];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> arr[i][j];
        }
    }
    dp[0][0] = arr[0][0];   //첫번째 집을 R로 색칠
    dp[0][1] = arr[0][1];   //첫번째 집을 G로 색칠
    dp[0][2] = arr[0][2];   //첫번째 집을 B로 색칠
 
    for (int i = 1; i < N; i++) {
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0];   //i번째 집을 R로 색칠 
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1];   //i번째 집을 G로 색칠 
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2];   //i번째 집을 B로 색칠 
    }
    cout << min(min(dp[N - 1][0], dp[N - 1][1]), dp[N - 1][2]);
 
 
}