백준 1149번: RGB거리

문제

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

1149번: RGB거리

---

풀이

n개의 집을 맞춰 빨강, 초록, 파랑 중 하나의 색으로 칠해야 하고 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하는 문제입니다.

1. 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
2. n번 집의 색은 n-1번 집의 색과 같지 않아야 한다.
3. i(2 ≤ i ≤ n-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

---

코드

자바

탑다운 방식을 이용한 코드입니다.

모든 입력이 끝나면 i를 포함한 for문을 이용해서 1번 집을 칠하는 색깔별 비용(cost[1][i])을 dp[1][i]에 넣습니다.

paintCost 함수의 반환값(dp[idx][color])은 idx번 집을 color로 칠했을 때 1번부터 idx번 집까지 칠했을 때 비용의 최솟값을 의미합니다.

dp[idx][color]가 0이 아니라면 그 값을 반환하고, 0이라면 때문에 집을 칠하는 규칙에 따라 paintCost(idx - 1, color가 아닌 2가지 색) 중 더 작은 값을 dp[idx][color]에 넣은 후 반환합니다.

위의 내용을 이용하여 paintCost(n, 3가지 color) 중 최솟값을 구하여 출력합니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    final static int red = 0, green = 1, blue = 2;
    static int[][] cost, dp;

    public static int paintCost(int idx, int color) {
        if (dp[idx][color] == 0) {
            if (color == red) {
                dp[idx][color] = Math.min(paintCost(idx - 1, green), paintCost(idx - 1, blue)) + cost[idx][red];
            } else if (color == green) {
                dp[idx][color] = Math.min(paintCost(idx - 1, red), paintCost(idx - 1, blue)) + cost[idx][green];
            } else {
                dp[idx][color] = Math.min(paintCost(idx - 1, red), paintCost(idx - 1, green)) + cost[idx][blue];
            }
        }
        return dp[idx][color];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        cost = new int[n + 1][3];
        dp = new int[n + 1][3];
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            cost[i][red] = Integer.parseInt(st.nextToken());
            cost[i][green] = Integer.parseInt(st.nextToken());
            cost[i][blue] = Integer.parseInt(st.nextToken());
        }
        for (int i = red; i <= blue; i++) {
            dp[1][i] = cost[1][i];
        }
        int min = paintCost(n, red);
        for (int i = green; i <= blue; i++) {
            min = Math.min(min, paintCost(n, i));
        }
        System.out.println(min);
    }
}

C언어

바텀업 방식을 이용한 코드입니다.

애초에 입력을 cost가 아닌 dp에 받으며 i를 이용한 for문을 이용하여 dp[i][3가지 color]에 dp[i - 1][color가 아닌 2가지 색] 중 더 작은 값을 dp[i][color]에 더해가며 1번부터 i번 집까지 칠하는 비용의 최솟값을 최신화합니다.

for문이 끝나면 dp[n][3가지 color] 중 최솟값을 구하여 출력합니다.

#include <stdio.h>
#include <stdlib.h>
#define math_min(a, b) a < b ? a : b
const int red = 0, green = 1, blue = 2;
main() {
	int n;
	scanf("%d", &n);
	int** dp = (int**)malloc(sizeof(int*) * (n + 1));
	for (int i = 1; i <= n; i++) {
		dp[i] = (int*)malloc(sizeof(int) * 3);
		scanf("%d %d %d", &dp[i][red], &dp[i][green], &dp[i][blue]);
	}
	for (int i = 2; i <= n; i++) {
		dp[i][red] += math_min(dp[i - 1][green], dp[i - 1][blue]);
		dp[i][green] += math_min(dp[i - 1][red], dp[i - 1][blue]);
		dp[i][blue] += math_min(dp[i - 1][red], dp[i - 1][green]);
	}
	int result = dp[n][red];
	for (int i = green; i <= blue; i++) {
		result = math_min(result, dp[n][i]);
	}
	printf("%d", result);
}

 

---

결론

다이나믹 프로그래밍을 이해하는 데에 도움이 되는 여러 가지 유형의 문제 중 하나였다고 생각합니다. 저는 dp 문제를 풀 때 바텀업 방식보다 탑다운 방식이 더 익숙하지만 앞으로 두 가지 방식 모두 익숙해져서 관련 코드 작성에 도움이 되면 좋겠다는 생각을 하였습니다.