백준 1149번 : RGB거리

• 분류: 다이나믹 프로그래밍

코드

#include <iostream>
using namespace std;

int cost[1001][3];
int table[1001][3];

int dp(int depth, int ban) {
    if(depth==1) {
        int min=INT32_MAX;
        for(int i=0 ; i<3 ; i++) {
            if(i==ban) continue;
            if(cost[depth][i]<min) min=cost[depth][i];
        }
        return min;
    }
    if(table[depth-1][0]==-1) table[depth-1][0] = dp(depth-1, 0);
    if(table[depth-1][1]==-1) table[depth-1][1] = dp(depth-1, 1);
    if(table[depth-1][2]==-1) table[depth-1][2] = dp(depth-1, 2);

    int case0 = table[depth-1][0];
    int case1 = table[depth-1][1];
    int case2 = table[depth-1][2];

    if(ban==0) return min(case1+cost[depth][1], case2+cost[depth][2]);
    else if(ban==1) return min(case0+cost[depth][0], case2+cost[depth][2]);
    else return min(case1+cost[depth][1], case0+cost[depth][0]);
}

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

• 코멘트
  
  n번째 집까지 칠했을 때 최소 비용 = min3(
  
  1. [n번째 집이 빨강일 때 (n-1)번째 집까지 칠했을 때의 최소 비용] + n번째 집 빨강 비용
  2. [n번째 집이 파랑일 때 (n-1)번째 집까지 칠했을 때의 최소 비용] + n번째 집 파랑 비용
  3. [n번째 집이 초록일 때 (n-1)번째 집까지 칠했을 때의 최소 비용] + n번째 집 초록 비용 )
     

이걸 dp로 구현하면 된다.
사실 반대로 하는 게 백 배 나은데.. 과거의 나는 그렇게 했었지만 퇴화해 버렸다.