백준 01149 - RGB거리

출처 : www.acmicpc.net/problem/1149

1149번: RGB거리

고려사항

- 메모제이션을 이용시에 지금 구하려는 곳으로 도달할 수 있는 경우의 수가 2가지임을 파악.

ex) n 번째 집을 1(G) 컬러로 색칠할 시, n-1 번째 집은 0(R) 과 2(B) 컬러임 => 둘중 작은 비용에 현재 비용 더해서 메모.

- n번째 집이 각각 RGB 컬러로 칠해지는 3가지 최소 비용 값이 memo[n-1][] 에 담겨있으니 최소값 구하기!

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

int n;
int rgb[1000][3];
int memo[1000][3];

int dp(int idx, int color){
    int &minV = memo[idx][color];

    if(idx == 0){
        minV = rgb[idx][color];
        return minV;
    }

    if(memo[idx][color] != 0){
        return minV;
    }

    if(color == 0){
        minV = min(dp(idx-1,1), dp(idx-1,2)) + rgb[idx][0];
    }else if(color == 1){
        minV = min(dp(idx-1,0), dp(idx-1,2)) + rgb[idx][1];
    }else{
        minV = min(dp(idx-1,0), dp(idx-1,1)) + rgb[idx][2];
    }

    return minV;
}

int main() {
    int minR, minG, minB, ans;

    cin>>n;
    for(int i=0;i<n;++i){
        cin>>rgb[i][0]>>rgb[i][1]>>rgb[i][2];
    }

    minR = dp(n-1,0);
    minG = dp(n-1,1);
    minB = dp(n-1,2);

    ans = min(minR, minG);
    ans = min(ans, minB);
    cout<<ans;

    return 0;
}