[#1149] RGB거리

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<vector<int>> cache;  //cache[i][j]는 i번째 집을 j색으로 칠했을 때 최소값
vector<vector<int>> cost;   //cost[i][j]는 i번째 집을 j색으로 칠할 때 드는 비용
 
int main() {
    int n;
    cin >> n;
 
    cost = vector<vector<int>>(n, vector<int>(3));
    cache = vector<vector<int>>(n, vector<int>(3, -1));
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> cost[i][j];
        }
    }
 
    cache[0][0] = cost[0][0];
    cache[0][1] = cost[0][1];
    cache[0][2] = cost[0][2];
 
    for (int i = 1; i < n; i++) {
        //현재집을 빨간색으로 칠할때
        cache[i][0] = min(cache[i - 1][1], cache[i - 1][2]) + cost[i][0];
 
        //현재집을 초록색으로 칠할때
        cache[i][1] = min(cache[i - 1][0], cache[i - 1][2]) + cost[i][1];
 
        //현재집을 빨간색으로 칠할때
        cache[i][2] = min(cache[i - 1][0], cache[i - 1][1]) + cost[i][2];
    }
 
    cout << min(cache[n - 1][0], min(cache[n - 1][1], cache[n - 1][2]));
 
    return 0;
}

한달전쯤 풀었던건데 기억이 안나서 다른분들이 푸신 힌트를 조금 보고 풀었다...ㅠㅠ

 

DP를 쓸때에는

1. 작은 수일때부터 어떻게 푸는지 생각해보기

2. 점화식 구해보기

 

이 문제에 적용시켜보면

1. n이 2라면

- 두번째 집을 빨간색으로 칠했을 때: 첫번째집은 초록 아니면 파란색

- 두번째 집을 초록색으로 칠했을 때: 첫번째집은 빨강 아니면 파란색

- 두번째 집을 파란색으로 칠했을 때: 첫번째집은 빨강 아니면 초록색

 

2. 

- 두번째 집을 빨간색으로 칠했을 때 최소비용: min(첫번째집을 초록, 파란색) + 두번째 집을 빨강 비용

- 두번째 집을 초록색으로 칠했을 때 최소비용: min(첫번째집을 빨강, 파란색) + 두번째 집을 초록 비용

- 두번째 집을 파란색으로 칠했을 때 최소비용: min(첫번째집을 빨강, 초록색) + 두번째 집을 파랑 비용

 

여기서 첫항 min은 cost가 아니가 cache여야 한다. 왜냐면 0번째 집부터 차례대로 칠하고 있기때문에

 

따라서

cache[n][0] = min(cache[n-1][1], cache[n-1][2]) + cost[n][0]

cache[n][1] = min(cache[n-1][0], cache[n-1][2]) + cost[n][1]

cache[n][2] = min(cache[n-1][0], cache[n-1][1]) + cost[n][2]

 

cache[n][ ]의 최소값이 답이 된다.