[1149] RGB거리

RGB거리(문제 _ 1149)

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보다 작거나 같은 자연수이다.

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

예제

3
26 40 83
49 60 57
13 89 99
answer : 96

풀이

<dp 문제>

i번째 집을 빨간색, 초록색, 파란색으로 칠할 때의 최솟값을 구하면 된다.
i번째 집을 칠할 때는 i-1번째 집이 칠해진 값 + 현재 칠하는 값(빨/초/파)이 들기 때문에 dp[i-1]값 + arr[i]를 하면 된다.

하지만 이번 문제에서는 i번째 집은 이웃된 집과 색이 같으면 안된다는 조건이 있기 때문에 3차원 배열을 이용해 계산해야 한다.

즉,

    dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0]; // 빨간색으로 칠할 경우
    dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1]; // 초록색으로 칠할 경우
    dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2]; // 파란색으로 칠할 경우

i번째 집을 빨간색으로 칠할 경우는 i-1번째 집을 (파,초) 로 칠했을 경우만 칠할 수 있다.
i번째 집을 초록색으로 칠할 경우는 i-1번째 집을 (빨,파) 로 칠했을 경우만 칠할 수 있다.
i번째 집을 파란색으로 칠할 경우는 i-1번째 집을 (빨,초) 로 칠했을 경우만 칠할 수 있다.

그렇기 때문에 최솟값을 계산할 때도 i-1번째 집의 일부 색깔의 값만 이용해서 계산한다.

코드

int  arr[1001][3];
int  dp[1001][3]; // i번째 집이 빨,초,파로 칠했을 때의 최솟값
int n;

int  main() {
    ios::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);
    cin >> n;

    for (int i = 0; i < n; i++) // 빨, 초, 파
    {
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
    }

    dp[0][0] = arr[0][0]; dp[0][1] = arr[0][1]; dp[0][2] = arr[0][2];

    for (int i = 1; i < n; i++)
    {
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0]; // 빨간색으로 칠할 경우
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1]; // 초록색으로 칠할 경우
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2]; // 파란색으로 칠할 경우
    }

    cout << min({ dp[n - 1][0],dp[n - 1][1],dp[n - 1][2] });
}