[백준] 1149. RGB거리

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

 

인접한 집의 색이 같으면 안된다는 규칙을 전제로 모든 집을 Red, Green, Blue 중 하나씩으로 칠할 때 모든 집을 칠하는 비용의 최솟값을 구하는 문제이다.

 

처음에 칠할 수 있는 경우의 수가 3가지이고, 무엇으로 칠하냐에 따라 다음 집을 칠할 수 있는 경우의 수도 달라지기 때문에 DP를 이용하여 풀 수 있다.

 

점화식은 다음과 같다.

d[i] = i-1번째 집까지의 최소비용 + i번째 집을 칠할 수 있는 색상 중 최소비용

top-down 형식으로 재귀함수를 이용하여 해결하였는데, 재귀함수 내부 내용은 다음과 같다.

이전 집이 R이면
res = (다음 집이 G일때와 다음 집이 B일때 중 비용이 더 적은 경우가 나오는 것으로 선택)

이전 집이 G이면
res = (다음 집이 R일때와 다음 집이 B일때 중 비용이 더 적은 경우가 나오는 것으로 선택)

이전 집이 B이면
res = (다음 집이 R일때와 다음 집이 G일때 중 비용이 더 적은 경우가 나오는 것으로 선택)

 

중간에 d[depth][rgb중 하나]를 저장하여 이미 확인한 경우의 수는 다시 탐색할 필요 없도록 하여 시간을 절약했다.

 

---

C

#include <stdio.h>
#include <string.h>

int d[1000][3];
int cost[1000][3];
int n;

int dp(int depth, int rgb_v){
    if(depth == n-1) return cost[depth][rgb_v];

    if(d[depth][rgb_v] != 0) return d[depth][rgb_v] + cost[depth][rgb_v];

    int a, b;
    if(rgb_v == 0){
        a = dp(depth+1, 1);
        b = dp(depth+1, 2);
        d[depth][rgb_v] = (a < b) ? a : b;
        return d[depth][rgb_v] + cost[depth][rgb_v];
    }
    else if(rgb_v == 1){
        a = dp(depth+1, 0);
        b = dp(depth+1, 2);
        d[depth][rgb_v] = (a < b) ? a : b;
        return d[depth][rgb_v] + cost[depth][rgb_v];
    }
    else{
        a = dp(depth+1, 0);
        b = dp(depth+1, 1);
        d[depth][rgb_v] = (a < b) ? a : b;
        return d[depth][rgb_v] + cost[depth][rgb_v];
    }

}

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < 3; j++) scanf("%d", &cost[i][j]);

    int start_r = dp(0, 0);
    int start_g = dp(0, 1);
    int start_b = dp(0, 2);

    if(start_r < start_b)
        printf("%d", (start_r < start_g) ? start_r : start_g);
    else
        printf("%d", (start_b < start_g) ? start_b : start_g);
}

---

Python

import sys
sys.setrecursionlimit(10**6)

def dp(depth, rgb_v): # rgb_v: 0->R, 1->G, 2->B
    global cost; global d

    if depth == n-1: return cost[depth][rgb_v] # base check

    if d[depth][rgb_v] != -1: return d[depth][rgb_v] + cost[depth][rgb_v] # 저장된 값 활용

    if rgb_v == 0:
        t = [dp(depth+1, 1), dp(depth+1, 2)]
        d[depth][rgb_v] = min(t)
        
        return d[depth][rgb_v] + cost[depth][rgb_v]
    elif rgb_v == 1:
        t = [dp(depth+1, 0), dp(depth+1, 2)]
        d[depth][rgb_v] = min(t)
        return d[depth][rgb_v] + cost[depth][rgb_v]
    else:
        t = [dp(depth+1, 0), dp(depth+1, 1)]
        d[depth][rgb_v] = min(t)
        return d[depth][rgb_v] + cost[depth][rgb_v]

n = int(input())
cost = []
d = [[-1 for _ in range(3)] for _ in range(n)]
for i in range(n):
    cost.append(list(map(int, input().split())))

start_r = dp(0, 0)
start_g = dp(0, 1)
start_b = dp(0, 2)
res = [start_r, start_g, start_b]

print(min(res))