[Baekjoon] 1149 - RGB

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

[재귀함수 활용]

#include <stdio.h>
#include <stdlib.h>
 
int houseCount;
int houseColor[1000][3];
 
int min(int a, int b)
{
    return a > b ? b : a;
}
 
int GetPaintCost(int n, int color)
{
    if(n == houseCount)
        return 0;
    
    
    // 다음 위치 색상을 정해야 한다.
    // 내 색이 아닌 것 중에 고른다.
    int cost = 0;
 
    if(color == 0) cost = min(GetPaintCost(n + 1, 1), GetPaintCost(n + 1, 2));
    if(color == 1) cost = min(GetPaintCost(n + 1, 0), GetPaintCost(n + 1, 2));
    if(color == 2) cost = min(GetPaintCost(n + 1, 0), GetPaintCost(n + 1, 1));
    
    
    
    return cost + houseColor[n][color];
}
 
 
int main() {
    scanf("%d\n", &houseCount);
    
    for(int i = 0; i < houseCount; i++){
        scanf("%d", &houseColor[i][0]);
        scanf("%d", &houseColor[i][1]);
        scanf("%d", &houseColor[i][2]);
    }
    
    // 처음 위치에 정한 색상 r,g,b 중 최소값
    int cost = min(min(GetPaintCost(0, 0), GetPaintCost(0, 1)), GetPaintCost(0, 2));
    
    printf("%d\n", cost);
    
    
    return 1;
}

[동적 계획법 활용]

#include <stdio.h>
#include <stdlib.h>
 
int houseCount;
int Cost[1000];
 
int min(int a, int b)
{
    return a > b ? b : a;
}
 
int main() {
    int r = 0, g = 0, b = 0;
    int prevR = 0, prevG = 0, prevB = 0;
    scanf("%d\n", &houseCount);
    
    for(int i = 0; i < houseCount; i++){
        prevR = r;
        prevG = g;
        prevB = b;
        
        scanf("%d", &r);
        scanf("%d", &g);
        scanf("%d", &b);
        
        r = min(prevG, prevB) + r;
        g = min(prevR, prevB) + g;
        b = min(prevR, prevG) + b;
    }
    int result = min(min(r, g), b);
    printf("%d", result);
    
    
    return 1;
}

i 의 비용 =  (i - 1) 의 비용 + i 에 칠할 색의 비용

i 에 칠할 r, g, b 에 대하여 각각 (i - 1) 의 색과 겹치지 않도록

r = (i - 1)의 g, b 중 작은 것,

g = (i - 1)의 r, b 중 작은 것

b = (i - 1)의 r, g 중 작은 것    ... 식으로 계산