백준) 1149 RGB거리

RGB거리

https://www.acmicpc.net/problem/1149

각 집들을 칠하는데 비용을 최소화해야 한다.

칠하는 색은 세 종류가 있고, 각 집마다 세가지 색을 칠하는 비용이 다르게 주어진다.

또한 이웃집의 색이 같을 수 없다. 0번 집을 빨갛게 칠했으면, 1번 집은 다르게 칠해야 한다.

모든 경우를 탐색한다면 3 ^ n 만큼 걸린다.

하지만 규칙에 따르면 같은 색을 연속해서 쓸 수 없고, 비용은 최소화해야 하기 때문에

다이나믹 프로그래밍으로 조질 수 있겠다.

n개째 집을 칠하는 비용은 n-1개의 집을 칠하는 최소비용에 더해지기 때문이다.

각 상태는 몇 번째 집을 칠하고 있는지, 색은 무엇인지로 구분된다.

배열은 dp[집의 수][색의 종류]로 잡자.

집을 앞에서 부터 연속적으로 칠한다면, 함수는 다음과 같다.

func(int num, int color) = num번째 집을 color로 칠하는 최소비용을 계산해줌.

그러면 정답은 func(n-1, 0), func(n-1, 1), func(n-1, 2) 중에 작은 값이다.

함수는 다음과 같이 퍼진다.

색을 0으로 칠했다면 최소비용은 func(n-1, 1)과 func(n-1, 2)중에 있다.

계속 퍼져나가다가 n==0이 되면 더 이상 퍼지지 않는다.

#include <stdio.h>
#include <string.h>
#include <algorithm>
 
#define init -987654321
 
int n;
int dp[1000][3];
int cost[1000][3];
 
 
int func(int num, int color) {
    if (num == 0)
        return cost[0][color];
 
    int& ref = dp[num][color];
    if (ref != init)
        return ref;
 
    int min = -init;
    for (int i = 0; i < 3; ++i) {
        if (i == color)
            continue;
 
        int t = func(num - 1, i);
        if (min > t)
            min = t;
    }
 
    return ref = min + cost[num][color];
}
 
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            scanf("%d", &cost[i][j]);
            dp[i][j] = init;
        }
    }
 
    int ans = -init;
    for (int i = 0; i < 3; ++i) {
        if (ans > func(n - 1, i))
            ans = dp[n - 1][i];
    }
    printf("%d", ans);
}