[BOJ-1463][DP] 1로 만들기 - Java

문제 바로가기

1463번: 1로 만들기

 N이 주어지면 1) 1을 빼거나, 2) 2의 배수면 2로 나누거나, 3) 3의 배수면 3으로 나누는 세가지 액션 중 하나를 해서 1로 만드는 최소 횟수를 구하는 문제입니다.

기본적인 Dynamic Programming 문제입니다.. DP는 메모이제이션(Memoization)이란 기술을 사용해서 풉니다. 메모이제이션이란 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술입니다.

 

DP를 푸는 방법은 크게 Top-Down 방식과 Bottom-Up 방식이 있습니다.

 

Top-Down은 말 그대로 위(N)에서 내려가면서 답을 구하는 방식입니다. Recursive하게 짜면 됩니다.

import java.util.Scanner;

public class Main {
    static int[] dp;
    public static int make(int n){
        if(n == 1) return 0;
        if (dp[n] != 0) return dp[n];

        int ans = make(n-1) + 1;
        if(n % 2 == 0) ans = Math.min(ans, make(n/2) + 1);
        if(n % 3 == 0) ans = Math.min(ans, make(n/3) + 1);
        dp[n] = ans;

        return ans;
    }
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        dp = new int[N + 1];
        input.close();

        System.out.println(make(N));
    }
}

dp[n]에는 n이 되는데 사용되는 최소한의 횟수를 저장합니다.

참고로 재귀함수는 메모리를 많이 차지하고, 반복문에 비해 성능이 많이 느립니당..

 

 

두번째 방식인 Bottom-Up은 밑에서부터 올라가면서 문제를 해결하는 방법입니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int[] dp = new int[N + 1];
        input.close();

        for(int i=2; i<=N;i++){
            dp[i] = dp[i-1] + 1;
            if(i % 2 == 0) dp[i] = Math.min(dp[i], dp[i/2] + 1);
            if(i % 3 == 0) dp[i] = Math.min(dp[i], dp[i/3] + 1);
        }

        System.out.println(dp[N]);
    }
}

돌아가는 로직은 크게 다르지 않고, 작은 수부터 반복문을 이용해 N까지의 값을 구해줍니다.

 

위에서부터 Top-Down, Bottom-up, Bottom-up, Top-Down

확실히 C++에 비해 많이 느림미다..

감사합니다 ^_^