dp PS #boj 17404

문제

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

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

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

입력

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

출력

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

풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define FASTIO   cin.tie(0);  cout.tie(0); ios_base::sync_with_stdio(0);
int dp[100001];
int a[1001][3]; //집 색칠 가격

int main() {
    FASTIO;
    int n;
    cin >> n;
    for (int i = 1; i < n+1; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> a[i][j]; 
        }
    }

기본 설정

for (int k=0; k<=2; k++) { // house1's color
        for (int j=0; j<=2; j++) { //ㄱ
            if (j == k) {
                d[1][j] = a[1][j];
            } else {
                d[1][j] = 1000*1000+1;
            }
        }
        for (int i=2; i<=n; i++) { //ㄴ
            d[i][0] = min(d[i-1][1], d[i-1][2]) + a[i][0];
            d[i][1] = min(d[i-1][0], d[i-1][2]) + a[i][1];
            d[i][2] = min(d[i-1][0], d[i-1][1]) + a[i][2];
        }
        for (int j=0; j<=2; j++) { //ㄷ
            if (j == k) continue;
            ans = min(ans, d[n][j]);
        }
    }
    cout << ans << '\n';
    return 0;
}

점화식 정의

dp[i][j] = i번째를 j색으로 칠할 때의 최소가격

ㄱ.

1번 집의 색상을 고정시키고 해당 색상으로 칠할 때의 초기 비용을 설정. 나머지 색상에 대해서는 매우 큰 수를 할당하여 선택되지 않도록 한다.
(첫 번째 집의 색을 각각 빨강, 초록, 파랑으로 고정하고, 각 경우에 대해 최소 비용을 계산하기 위해서)

ㄴ. 점화식 이용

2번 집부터 N번 집까지 각 집을 칠하는 최소 비용을 위의 점화식을 사용하여 계산. 이 과정에서 각 집을 칠하는 최소 비용은 바로 이전 집의 색상에 따라 달라짐

ㄷ. 마지막 집 색 고려 (첫번째 집과 같은 경우 배제)

N번 집을 제외한 나머지 집들에 대해 계산된 최소 비용 중 최소값을 찾는다 단, 1번 집과 색상이 같은 경우는 제외함(continue;로 구현)