1149. RGB거리 (자바, Java)

동적계획법은 메모이제이션이라는 기법을 이용해서, 반복문이나 재귀를 돌리면서 이미 알아낸 값을 기록해가며 문제를 해결하는 기법이다.

 

Top-Down 방식으로 하는 경우, 재귀를 이용해서 한계단씩 내려가는 방법을 쓰게 되고,

Bottom-Up 방식으로 하는 경우, 반복문을 이용해서 처음부터 하나씩 올라가는 방법을 쓰게 된다.

 

문제를 풀 때, 아직 동적계획법에 대한 감이 잡힐랑 말랑 해서,

일단 백트래킹으로 풀었으나, ide에서는 작동하였음에도

백준에서는 시간초과가 나와버렸다. 값을 기록하지않고, 구했던 값을 또 구하다보니 성능에서 차이가 생긴 모양.

 

1. 백트래킹으로 푼 풀이, 시간 초과.

 

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

public class Main {

    static int[][] cost; // 각 비용을 담을 배열
    static int min = Integer.MAX_VALUE; // 정답이 될 최솟값을 저장.
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        cost = new int[n][3];

        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j=0; j<=2; j++) {
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        coloring(0, 0, -1);
        System.out.println(min);
    }

    // 색칠하기
    static void coloring(int depth, int sum, int prevColor) {

        if (depth==n) {
            min = Math.min(min, sum);
            return;
        }

        for (int i=0; i<=2; i++) {
            if (i != prevColor) {
                coloring(depth + 1, sum + cost[depth][i], i);
            }
        }
    }
}

 

레퍼런스를 찾아 동적계획법으로 풀이.

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

public class Main {

    static int[][] cost; // 각 비용을 담을 배열
    static int n;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        cost = new int[n][3];
        dp = new int[n][3];

        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j=0; j<=2; j++) {
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i=0; i<=2; i++) {
            dp[0][i] = cost[0][i];
        }

        System.out.println(Math.min(Math.min(coloring(n-1, 0), coloring(n-1, 1)), coloring(n-1, 2)));
    }

    // 색칠하기
    static int coloring(int n, int color) {

        // 탐색하지 않은 배열인 경우, 탐색하여 값을 입력한다.
        if (dp[n][color] == 0) {

            if (color==0) {
                dp[n][color] = Math.min(coloring(n-1, 1), coloring(n-1, 2)) + cost[n][color];
            }

            else if (color==1) {
                dp[n][color] = Math.min(coloring(n-1, 0), coloring(n-1, 2)) + cost[n][color];
            }

            else if (color==2) {
                dp[n][color] = Math.min(coloring(n-1, 0), coloring(n-1, 1)) + cost[n][color];
            }
        }
        
        return dp[n][color];
    }
}

 

본래 동적계획법 쪽은 Top-down 으로 한 번,

Bottom-up으로 한 번 풀려고 했는데

어쩌다보니 후자를 생략해버렸네요..