문제

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

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

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

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

코드

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

int main()
{
    int n;
    cin >> n;
    int arr[1002][4];
    int dp[1002][4];
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=3;j++)
            cin >> arr[i][j];
    }
    dp[1][1] = arr[1][1];
    dp[1][2] = arr[1][2];
    dp[1][3] = arr[1][3];
    for(int i=2;i<=n;i++) {
        dp[i][1] = min(dp[i-1][2], dp[i-1][3]) + arr[i][1];
        dp[i][2] = min(dp[i-1][1], dp[i-1][3]) + arr[i][2];
        dp[i][3] = min(dp[i-1][1], dp[i-1][2]) + arr[i][3];
    }
    cout << min({dp[n][1], dp[n][2], dp[n][3]});
    return 0;
}

• 가장 핵심은, 연속한 두 집의 색은 반드시 달라야한다는 점이다.
• 배열 arr는 색에 따른 각 집의 비용을 저장한 것이고, dp는 각 색을 선택했을 때 i번째 집에서의 누적 최소비용이다.
  • dp를 구할 때, 빨, 초, 파 각각의 색을 선택했을 때의 최소비용 모두를 저장한 뒤, 마지막 집에서 색을 선택할 때 가장 적은 값을 출력하면 된다.