[백준] 1149번: RGB거리

흐흐 기분 좋당 답 안 보고 푼 첫 문제당

import java.util.Arrays;
import java.util.Scanner;

public class boj1149 {
    static int N;
    static int[][] cost;
    static int[][] dp;
    static int solve(int i, int rgb) {
        if(i == N-1) {
            return dp[i][rgb] = cost[i][rgb];
        }
        if(dp[i][rgb] != 0)
            return dp[i][rgb];
        switch(rgb) {
            case 0:
                dp[i][rgb] = cost[i][rgb] + Math.min(solve(i+1, 1), solve(i+1, 2));
                break;
            case 1:
                dp[i][rgb] = cost[i][rgb] + Math.min(solve(i+1, 0), solve(i+1, 2));
                break;
            case 2:
                dp[i][rgb] = cost[i][rgb] + Math.min(solve(i+1, 0), solve(i+1, 1));
                break;
            default:
                return 0;
        }
        return dp[i][rgb];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        cost = new int[N][3];
        dp = new int[N][3];
        for(int i = 0; i < N; i++) {
            cost[i][0] = sc.nextInt();
            cost[i][1] = sc.nextInt();
            cost[i][2] = sc.nextInt();
        }
        int[] res = new int[3];
        res[0] = solve(0, 0); res[1] = solve(0, 1); res[2] = solve(0, 2);
        Arrays.sort(res);
        System.out.println(res[0]);
    }
}

허허 근데 이거는 저장해놓고 끌어다 쓰는 게 더 비효율적인 문제였나보다. 다른 답들을 참고해서, 탑다운 재귀함수가 아니라 바텀업 반복문을 사용했다.

import java.util.Arrays;
import java.util.Scanner;

public class boj1149 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] cost = new int[N+1][3];
        for(int i = 1; i <= N; i++) {
            cost[i][0] = sc.nextInt();
            cost[i][1] = sc.nextInt();
            cost[i][2] = sc.nextInt();
        }
        int[][] sol = new int[N+1][3];

        for(int i = 1; i <= N; i++) {
            sol[i][0] = cost[i][0] + Math.min(sol[i-1][1], sol[i-1][2]);
            sol[i][1] = cost[i][1] + Math.min(sol[i-1][0], sol[i-1][2]);
            sol[i][2] = cost[i][2] + Math.min(sol[i-1][0], sol[i-1][1]);
        }

        Arrays.sort(sol[N]);
        System.out.println(sol[N][0]);
    }
}

코드가 훨씬 간결하고 시간도 빨리 나왔다. 하씨 어떨 때 어떤 방법을 써야하는 지 찾아봐야겠다.