[백준 알고리즘 1464] 1로 만들기 - java(Dynamic Programming)

다이나믹 프로그래밍을 푸는 첫 번째 과정은 DP[n] (또는 k차원의 배열]이 무엇인지를 정의하는 것이다.

일반적인 문제는 그대로 정의하면 된다.

이 문제에서는,

dp[n] = n을 1로 만드는 최소한의 연산의 수 

라고 생각할 수 있다.

또, dp[n]은 dp[n-1]+1, dp[n/2] +1, dp[n/3] +1 중 하나이고,

이전 단계 즉, N-1 또는 N/2 또는 N/3 을 1로 만드는 최소한의 연산의 수 라는 조건을 만족한다면,

N을 1로만드는 최소한의 연산의 수라는 조건도 만족한다.

간단한 문제이기 때문에 바로 코드,

Top-Down 방식으로 재귀 호출로 구현한 코드이다. 

d배열에 메모를 하는 방식이다. 

문제는 충분히 시간 안에 해결할 수 있지만 재귀 호출의 오버헤드 문제 때문인지 Bottom-up보단 좀 오래 걸렸다

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

public class Main {
	static int[] d=new int[1000001];
	public static int dp(int N) {
		if(N==0 || N==1)
			return 0;
		
		if(d[N]>0)
			return d[N];
		
		if(N%3==0 && N%2==0) {
			d[N]= Math.min(dp(N/3), Math.min(dp(N-1),dp(N/2)))+1;
		}else if(N%3==0) {
			d[N]= Math.min(dp(N/3),dp(N-1))+1;
		}else if(N%2==0) {
			d[N]= Math.min(dp(N/2), dp(N-1))+1;
		}else {
			d[N]= dp(N-1)+1;
		}
		return d[N];
		
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		int N=Integer.parseInt(br.readLine());
		
		System.out.println(dp(N));
		
		
	}

}

다음은 Bottom-up -> for문 방식

전역 변수의, 재귀 호출의 부담이 없다. 

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		int N=Integer.parseInt(br.readLine());
		
		
		/*bottom-up*/
		int[] dp=new int[N+1];
		dp[0]=0; dp[1]=0;
		for(int i=2; i<=N; i++) {
			if(i%3==0 && i%2==0) {
				dp[i]=Math.min(dp[i/3], Math.min(dp[i-1],dp[i/2]))+1;
			}else if(i%3==0) {
				dp[i]=Math.min(dp[i/3],dp[i-1])+1;
			}else if(i%2==0) {
				dp[i]=Math.min(dp[i/2], dp[i-1])+1;
			}else {
				dp[i]=dp[i-1]+1;
			}
			
		}
		System.out.println(dp[N]);
		

	}

}