[백준] 1149 - RGB 거리 [JAVA]

 

코드(Top-down)

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

public class Main {

    final static int Red = 0;
    final static int Green = 1;
    final static int Blue = 2;

    static int[][] cost;
    static int[][] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        cost = new int[N][3]; // 각 색깔의 비용

        dp = new int[N][3]; // 누적합 저장

        for (int i = 0; i < N; i++) {
            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());
        }

        // dp 첫 번째 값 초기화
        dp[0][Red] = cost[0][Red];
        dp[0][Green] = cost[0][Green];
        dp[0][Blue] = cost[0][Blue];

        // 누적 중 가잡 낮은 값
        System.out.println(Math.min(paintHome(N - 1, Red), Math.min(paintHome(N - 1, Green), paintHome(N - 1, Blue))));
    }

    static int paintHome(int n, int color) {

        // 탐색 전이면
        if (dp[n][color] == 0) {

            if (color == Red) {
                dp[n][color] = Math.min(paintHome(n - 1, Green), paintHome(n - 1, Blue)) + cost[n][color];
            }
            else if (color == Green) {
                dp[n][color] = Math.min(paintHome(n - 1, Red), paintHome(n - 1, Blue)) + cost[n][color];
            }
            else {
                dp[n][color] = Math.min(paintHome(n - 1, Red), paintHome(n - 1, Green)) + cost[n][color];
            }

        }

        return dp[n][color];
    }

}

 

코드(Bottom-up)

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

public class Main {

    static int[][] cost;
    static int[][] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        dp = new int[N][3];
        cost = new int[N][3];

        StringTokenizer st;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            cost[i][0] = Integer.parseInt(st.nextToken());
            cost[i][1] = Integer.parseInt(st.nextToken());
            cost[i][2] = Integer.parseInt(st.nextToken());
        }
        dp[0][0] = cost[0][0];
        dp[0][1] = cost[0][1];
        dp[0][2] = cost[0][2];
        
        // Bottom-up 방식
        for (int i = 1; i < N; i++) {
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];
        }

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

}