백준 1149 (RGB거리) / C++

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

1149번: RGB거리

> 풀이

 

인접한 집의 색깔은 달라야 합니다. 따라서 dp를 사용해서 각 단계마다 색을 칠할 때 최솟값을 구할 수 있도록 쌓아가시면 됩니다.

 

예를 들어 파랑을 칠하려고 한다면 이전 집에서 빨강과 초록을 칠한 경우 중 작은 값에 파랑을 칠하면 되겠죠?

#include <bits/stdc++.h>
using namespace std;

int dp[1001][3];
int cost[1001][3];
int N;

int main(void)
{
        scanf("%d", &N);
        for (int i = 0; i < N; i++)
                scanf("%d %d %d", &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++) {
                dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
                dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
                dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];
        }
        
        sort(dp[N - 1], dp[N - 1] + 3);
        printf("%d", dp[N - 1][0]);
        
        return 0;
}

(개발 환경 : vs code)