문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

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

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

입력
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

접근

작년 6월에 한 번 시도해봤던 문제인데 그때 제대로 손도 못 대고 풀이를 봤었더라...
이번에는 dp 배열을 1차원으로 하려고 애쓰다가 괜히 어려운 길 돌아온 것 같긴 한데 2차원으로 푸니까 어렵지 않게 금방 풀렸다.

Bottom-Up 방식(반복문)의 풀이

지난번에 풀었을 땐 Top-Down 방식의 풀이를 봤던 것 같은데 지금 보니 이 문제는 Bottom-Up으로 접근하는 게 더 나은 선택인 것 같다. 순서대로 하나씩 dp 배열을 채워나가면 되니까. 이렇게 하면 한 번 이용한 입력 값을 다시 참조하지 않아서 입력 값을 굳이 다른 배열에 저장해둘 필요가 없기도 하다.

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] dp = new int[N][3];

        String[] input = br.readLine().split(" ");
        dp[0][0] = Integer.parseInt(input[0]);
        dp[0][1] = Integer.parseInt(input[1]);
        dp[0][2] = Integer.parseInt(input[2]);

        for (int i = 1; i < N; i++) {
            input = br.readLine().split(" ");
            int r = Integer.parseInt(input[0]);
            int g = Integer.parseInt(input[1]);
            int b = Integer.parseInt(input[2]);

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

        System.out.println(Math.min(dp[N - 1][0], Math.min(dp[N - 1][1], dp[N - 1][2])));
    }
}

Top-Down 방식(재귀)의 풀이

물론 Top-Down으로도 풀 수 있다!

import java.io.*;

class Main {
    static int N;
    static int[][] cost;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        cost = new int[N][3];
        dp = new int[N][3];
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            cost[i][0] = Integer.parseInt(input[0]);
            cost[i][1] = Integer.parseInt(input[1]);
            cost[i][2] = Integer.parseInt(input[2]);
        }
        dp[0][0] = cost[0][0];
        dp[0][1] = cost[0][1];
        dp[0][2] = cost[0][2];
        System.out.println(Math.min(calculateCost(N - 1, 0), Math.min(calculateCost(N - 1, 1), calculateCost(N - 1, 2))));
    }

    private static int calculateCost(int num, int color) {
        if (dp[num][color] == 0) {
            if (color == 0) {
                dp[num][color] = Math.min(calculateCost(num - 1, 1), calculateCost(num - 1, 2)) + cost[num][0];
            } else if (color == 1) {
                dp[num][color] = Math.min(calculateCost(num - 1, 0), calculateCost(num - 1, 2)) + cost[num][1];
            } else {
                dp[num][color] = Math.min(calculateCost(num - 1, 0), calculateCost(num - 1, 1)) + cost[num][2];
            }
        }
        return dp[num][color];
    }
}

6달 전 채점 결과가 Top-Down으로 풀이한 결과이고, 위 두 결과가 Bottom-Up으로 풀이한 결과이다. Bottom-Up으로 풀면 앞서 언급했듯 cost 배열을 사용할 필요가 없고, 입력과 동시에 for문 안에서 최소 비용을 바로 연산할 수 있기 때문에 시간 복잡도, 공간 복잡도를 모두 줄일 수 있다.