BOJ01149 RGB 사거리

https://www.acmicpc.net/problem/1149 (opens new window)

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

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

컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이다. 특정한 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있다. 바로 다이나믹 프로그래밍^{Dynamic Programing}이다.

제출 코드

중간 결과를 저장하기 위한 dp 배열을 선언한다.

int[][] dp = new int[n][3];

0 index는 red, 1 index는 green, 2 inde는 blue로 표현하여 저장한다.

for (int i = 0; i < n; i++) {
    int r = scanner.nextInt();
    int g = scanner.nextInt();
    int b = scanner.nextInt();

    rgbs[i][0] = r;
    rgbs[i][1] = g;
    rgbs[i][2] = b;
}

이제 집을 색칠해가며 중간 결과를 저장한다. 겹치지 않는 3가지 경우를 모두 조사하여 조건에 맞는 최소 비용을 구해서 저장한다.

for (int i = 0; i < n; i++) {
    if (i == 0) {
        dp[i][0] = rgbs[i][0];
        dp[i][1] = rgbs[i][1];
        dp[i][2] = rgbs[i][2];
        continue;
    }

    dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + rgbs[i][0];
    dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + rgbs[i][1];
    dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + rgbs[i][2];
}

아래는 제출한 최종 코드이다.

import java.util.Scanner;

public class BOJ1149 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[][] rgbs = new int[n][3];
        int[][] dp = new int[n][3];

        for (int i = 0; i < n; i++) {
            int r = scanner.nextInt();
            int g = scanner.nextInt();
            int b = scanner.nextInt();

            rgbs[i][0] = r;
            rgbs[i][1] = g;
            rgbs[i][2] = b;
        }

        for (int i = 0; i < n; i++) {
            if (i == 0) {
                dp[i][0] = rgbs[i][0];
                dp[i][1] = rgbs[i][1];
                dp[i][2] = rgbs[i][2];
                continue;
            }

            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + rgbs[i][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + rgbs[i][1];
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + rgbs[i][2];
        }

        int min = Integer.MAX_VALUE;
        for (int value : dp[n - 1]) {
            if (min > value) {
                min = value;
            }
        }

        System.out.println(min);
    }
}

#algorithm #BOJ #다이나믹 프로그래밍