문제

image.png

풀이

첫번째 집에서 최소비용이 드는 색을 선택한다. 그러면 두번째 집에서는 첫번째 집이 사용한 색을 제외한 것 중 최소비용이 드는 색을 선택하는 방식으로, 전체 집을 칠하는 최소 비용을 구할 수 있다.

K = 0(빨강),1(초록),2(파랑)이라고 가정하면 아래와 같은 형태로 표현된다.

cost[1][0] = 첫 번째 집을 칠하는 비용, 색은 빨강
cost[1][1] = 첫 번째 집을 칠하는 비용, 색은 초록
cost[1][2] = 첫 번째 집을 질하는 비용, 색은 파랑

전체 집을 칠할때 드는 최소 비용을 구해야 하므로 점화식은 "i번째 집까지 j색을 칠할때 드는 최소 비용" 이라고 정의할 수 있다.

dp[i][j] = 집 i를 j색으로 칠했을때 까지의 최소비용이라고 정의

dp[i][0] = min(dp[i-1][0],dp[i-1][1]) + cost[i][2]
dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + cost[i][1]
dp[i][2] = min(dp[i-1][1],dp[i-1][2]) + cost[i][0]

풀이


#include <stdio.h>
#include <algorithm>
using namespace std;
int dp[1001][4];
int a[1001][4];
int main(int argc, const char * argv[]) {


    int n;
    scanf("%d",&n);



        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= 3; j++) {
                scanf("%d",&a[i][j]);
            }
        }



    // 첫 번째 집 색칠 하는 가격 설정
    for(int i = 1; i <=3; i++) {
        dp[1][i] = a[1][i];


    }

    for(int i = 2; i <= n; i++) {

            dp[i][2] = min(dp[i-1][3], dp[i-1][1]) + a[i][2];
            dp[i][1] = min(dp[i-1][3], dp[i-1][2]) + a[i][1];
            dp[i][3] = min(dp[i-1][1], dp[i-1][2]) + a[i][3];

    }

    printf("%d",min(min(dp[n][1],dp[n][2]), dp[n][3]));


}