백준 17404번: RGB거리 2

문제

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

17404번: RGB거리 2

---

풀이

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

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

지난 RGB거리 문제에서 1번 집과 n번 집의 색이 같지 않아야 하는 조건이 1개 추가됐습니다.

---

코드

자바

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

모든 입력이 끝나면 i를 포함한 for문을 이용해서 dp배열을 초기화한 후에 paintCost(n, 3가지 color, 해당 color) 중 최솟값을 구합니다. 이때 지난 RGB거리 문제와 마찬가지로 paintCost 함수의 반환값(dp[idx][color])은 idx번 집을 color로 칠했을 때 1번부터 idx번 집까지 칠했을 때 비용의 최솟값을 의미합니다.

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

이후 idx가 1이 됐을 때 n번 집을 칠한 색(fix)과 1번 집을 칠할 색(color)이 같다면 조건을 만족하지 않으므로 dp[idx][color]에 2^31을 넣고 다르다면 cost[1][color]를 넣어서 무조건 paintCost(idx - 1, fix가 아닌 color)가 더 작은 값이 되도록 합니다.

위의 내용을 이용하여 구한 최솟값 min을 출력합니다.

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, int fix) {
        if (idx == 1) {
            if (color == fix) {
                dp[idx][color] = Integer.MAX_VALUE;
            } else {
                dp[idx][color] = cost[1][color];
            }
        }
        if (dp[idx][color] == 0) {
            if (color == 0) {
                dp[idx][red] = Math.min(paintCost(idx - 1, green, fix), paintCost(idx - 1, blue, fix)) + cost[idx][red];
            } else if (color == 1) {
                dp[idx][green] = Math.min(paintCost(idx - 1, red, fix), paintCost(idx - 1, blue, fix)) + cost[idx][green];
            } else {
                dp[idx][blue] = Math.min(paintCost(idx - 1, red, fix), paintCost(idx - 1, green, fix)) + 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];
        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());
        }
        int min = Integer.MAX_VALUE;
        for (int i = red; i <= blue; i++) {
            dp = new int[n + 1][3];
            min = Math.min(min, paintCost(n, i, i));
        }
        System.out.println(min);
    }
}

C언어

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

지난 RGB거리 문제에서의 바텀업 방식을 이용한 코드와 다르게 입력을 dp가 아닌 cost에 받습니다. i를 포함한 for문 안에서 j를 포함한 for문을 이용하여 1번 집의 색을 i로 칠하는 것을 기준으로 하기 위해 dp[1][i를 제외한 j]는 INF값을 넣어서 더 작은 값이 될 수 없게 설정합니다. 이때 INF는 n의 범위(2~1000)와 비용의 최댓값(1000)을 곱한 값입니다.

아래에 있는 j를 포함한 for문을 이용하여 dp[j][3가지 color]에 dp[j - 1][color가 아닌 2가지 색] 중 더 작은 값과 cost[j][color]을 더한 값을 dp[i][color]에 넣어가며 1번부터 j번 집까지 칠하는 비용의 최솟값을 최신화합니다.

이후 j를 포함한 for문을 1번 더 이용하여 i(1번집을 칠한 색)와 j(n번집을 칠할 색)가 다르면 dp[n][j]와 min을 비교해가며 최솟값을 구하여 출력합니다.

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

 

---

결론

다이나믹 프로그래밍을 이용하여 문제 조건에 맞게 초기값을 함수 또는 for문 안에서 다르게 설정해야 했던 문제였습니다. 또한 #define을 이용하여 최솟값을 구하기 위한 매크로 함수를 만들면 값이 다르게 나오는데 이 현상이 왜 발생하는지에 대해 알 수 없어서 일반적인 함수로 구현하여 해결했습니다.