[백준][JAVA] 1463번 1로 만들기

백준 1463번 문제 설명

다이나믹 함수 개념을 설명하기에 가장 대표적인 문제라고 할 수 있을 것 같다.

N에 괸한 최소값을 구하기 위해서 그 밑의 값들을 참조하는 형식이다. 이는 재귀함수의 원리와 같다고 볼 수 있지만, 재귀함수의 경우 함수 콜(call)을 계속해야하므로 시간이나 메모리에서 사용의 한계점이 존재한다.

이에 반해, 다이나믹 프로그래밍은 값을 구해 어레이 등에 저장함으로써 해당 값을 알 수 있게된다. 다이나믹 프로그래밍 개념의 경우 소스가 많이 존재함으로 각설하고, 알고리즘에 대해서 설명하겠다. 코드는 재귀함수와 다이나믹프로그래밍을 이용하여 구한 두가지를 모두 구현해보았지만, 재귀함수의 경우 백준에 제출하였을 때 시간초과가 뜬다.

 

N에 관한 연산 최소값을 구하기 위해 최대 세 종류의 값을 참조해야한다. 3으로 나눈 값, 2로 나눈 값, 1을 뺀 값.  

세 값 중 N을 3으로 나눈 값이 최소값이면 N은 이에 3을 곱해야하므로 연산이 하나 추가되게 된다. 즉, N에 관한 연산 최소값은 반대로 이들 중 최소값에 1을 더한 값이 된다. 구현된 재귀함수의 경우 이를 N에서 부터 top-down방식으로 구하는 것이고, 반대로 다이나믹 프로그래밍은 bottom-up방식으로 1부터 최소값을 구해나가며 최종 N값을 구하는 것이다.

 

 

전체 코드

1. 재귀함수 (top-down)

import java.lang.Math;
import java.util.Scanner; 

public class Main
{
    public static int solve(int N) {
        if (N == 1) return 0;
        
        if (N % 6 == 0) {
            return Math.min(Math.min(solve(N / 3), solve(N / 2)), solve(N-1)) + 1;
        } else {
            if (N % 3 == 0) {
                return Math.min(solve(N / 3), solve(N-1)) + 1;
            } else if (N % 2 == 0) {
                return Math.min(solve(N / 2), solve(N-1)) + 1;
            } else {
                return solve(N-1) + 1;
            }
        }
    }
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int N = sc.nextInt();
	    
	    System.out.println(solve(N));
	}
}

2. 다이나믹 프로그래밍 (bottom-up)

import java.lang.Math;
import java.util.Scanner; 

public class Main
{
    public static int solve(int N) {
        if (N == 1) return 0;
        
        int[] dp = new int[N + 1];
        dp[1] = 0;
        for (int i = 2; i <= N; i++) {
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i / 3], dp[i - 1]);
                if (i % 2 == 0) {
                    dp[i] = Math.min(dp[i], dp[i / 2]);
                }
                dp[i]++;
            } else {
                dp[i] = dp[i - 1];
                if (i % 2 == 0) {
                    dp[i] = Math.min(dp[i], dp[i / 2]);
                }
                dp[i]++;
            }
        }
        return dp[N];
    }
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int N = sc.nextInt();
	    
	    System.out.println(solve(N));
	}
}

 

결과화면