[1149] RGB 거리

http://boj.kr/1149

기본 DP2

- d[n][k] : n번째 집을 컬러 k로 칠했을 때, 1~n번째 집을 칠하는데 드는 최소비용.

#include <stdio.h>
 
int rgb[1001][3];
int d[1001][3];
 
int min(int a, int b)
{
    return a > b ? b : a;
}
 
int go(int n, int k)
{
    int ans;
 
    if(n == 0) return rgb[0][k];
    if(d[n][k]) return d[n][k];
 
    if(k == 0) {
        ans = go(n-1, 1);
        ans = min(ans, go(n-1, 2));
    }
    else if(k == 1) {
        ans = go(n-1, 0);
        ans = min(ans, go(n-1, 2));
    }   
    else {
        ans = go(n-1, 0);
        ans = min(ans, go(n-1, 1));
    }
    return d[n][k] = ans + rgb[n][k];
}
 
int main()
{
    int i, j, n;
    int ans;
    scanf("%d", &n);
    
    for(i=0; i<n; i++)
        for(j=0; j<3; j++)
            scanf("%d", &rgb[i][j]);;
 
    ans = go(n-1, 0);
    ans = min(ans, go(n-1, 1));
    ans = min(ans, go(n-1, 2));
    printf("%d\n", ans);
 
    return 0;
}

>> 실은 6개월전에 해결했던 문제다.

     하지만 과거에 코드를 보니, 한동안 ps를 안해서 그런지 더 멍청해진것 같다는 생각이 든다...

#include <stdio.h>
 
int rgb[1001][3], d[1001][3];
 
int min(int a, int b)
{
    return a > b ? b : a;
}
 
int go(int n, int color)
{
    int ret;
    if(n < 0) return 0; 
    if(d[n][color]) return d[n][color];    
    ret = go(n-1, (color+1)%3);
    ret = min(ret, go(n-1, (color+2)%3));    
    return d[n][color] = ret+rgb[n][color];
}
 
int main()
{
    int i, j, n, ans;
    scanf("%d", &n);
 
    for(i=0; i<n; i++) 
        for(j=0; j<3; j++) 
            scanf("%d", &rgb[i][j]);
    
    ans = go(n-1, 2);
    ans = min(ans, go(n-1, 1)); 
    ans = min(ans, go(n-1, 0)); 
    printf("%d\n", ans);
    return 0;
}

- 백준해설 

i번째 집의 이웃은 i-1번째 집과 i+1번째 집. (연속)

처음집과 마지막 집은 이웃이 아니다..!!

다이나믹에서 중요한 조건중에 하나인 "연속"이라는 조건이 포함된 문제..!!

앞의 집과의 색만 다르게 칠하면 된다.

- 아래 코드는 바텀업.

for(int i=1; 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][0];
    d[i][2] = min(d[i-1][0], d[i-1][1]) + a[i][0];
}
 
cout << min({d[n][0], d[n][1], d[n][2]}) << '\n';

>> 0번째는 비워두고 하는것이 좋다. 

>> min({a, b, c}); // a, b, c 중 최소값. 

>> c++11 문법으로 아래가 함수의 원형인 것 같다. 즉 리스트로 들어가서 그 리스트들 중 최소값이 

     리턴되는 방식인 것 같다.

template<class T>
T min( std::initializer_list<T> ilist)
{
    return *std::min_element(ilist.begin(), ilist.end());
}