[백준] 12852 1로 만들기 2 - DP JAVA

https://www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

코드설명

DP 혹은 재귀를 활용하여 해결할 수 있는 문제입니다.

하지만, DP를 활용해야 시간이 훨씬 빠르므로 DP를 활용합니다.

 

 

 

코드

bottom-up 방식

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

public class Main {
	public static int T, N;
	public static int answer = 0;
	public static int[] dp;
	public static int[] before;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	dp = new int[N+1];
    	before = new int[N+1];
    	
    	simulate();
    	
    	
    	System.out.println(dp[N]);
    	String str="";
    	while(N > 0) {
    		str += N +" ";
    		N = before[N];
    	}
    	System.out.println(str);
    }
    
    public static void simulate() {
    	dp[1] = 0;
    	for(int i=2; i<= N;i++) {
    		dp[i] = dp[i-1] + 1;
    		before[i] = i - 1;
    		
    		if(i % 3 == 0 && dp[i/3] + 1 < dp[i]) {
    			dp[i] = dp[i/3] + 1;
    			before[i] = i / 3;
    		}
    		if(i % 2 == 0 && dp[i/2] + 1 < dp[i]) {
    			dp[i] = dp[i/2] + 1;
    			before[i] = i / 2;
    		}
    	}
    }
   
}

 

 

TOP-DOWN 으로 풀어보려고했지만 실패한코드

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

public class Main {
	public static int T, N;
	public static int answer = 0;
	public static int[] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	dp = new int[10000001];
    	Arrays.fill(dp,  Integer.MAX_VALUE);
    	dp[N] = 0;
    	
    	simulate(N);

    	for(int i=N;i>=0;i--) {
    		System.out.print(" "+dp[i]);
    	}
    	System.out.println();
    	
    	System.out.println(dp[1]);
    	

    }
    
    public static void simulate(int num) {
    	

    	
    	if(num == 1) {
        	for(int i=N;i>=0;i--) {
        		System.out.print(" "+dp[i]);
        	}
        	System.out.println();    		
    		return;
    	}
    		
    	
    	if(num % 3 == 0) {
    		dp[num/3] = Math.min(dp[num/3], dp[num]) + 1;
    		System.out.println("Num/3:"+num/3);
    		simulate(num/3);
    	}
    	if(num % 2 == 0) {
    		dp[num/2] = Math.min(dp[num/2], dp[num]) + 1;
    		System.out.println("Num/2:"+num/2);
    		simulate(num/2);
    	}
    	dp[num-1] = Math.min(dp[num-1], dp[num]) + 1;
    	System.out.println("Num-1:"+(num-1));
    	simulate(num-1);

    }
   
}

 

재귀로 풀어본 코드

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

public class Main {
	public static int T, N;
	public static int answer = 0;
	public static String answerStr="";
	public static int[] dp;
	public static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	dp = new int[N+1];
    	
    	simulate(N, 0, "");

    	System.out.println(min);
    	System.out.println(N + answerStr);
    }
    
    public static void simulate(int num, int cnt, String str) {
    	
    	if(cnt >= min) {
    		return ;
    	}
    	
    	if(num == 1) {
    		if(cnt < min) {
    			min = cnt;
    			answerStr = str;
    		}
    		return ;
    	}
    	
    	if(num % 3 == 0) {
    		simulate(num / 3, cnt + 1, str + " "+ num/3);
    	}
    	if(num%2 == 0) {
    		simulate(num / 2, cnt + 1, str + " "+num/2);
    	}
    	simulate(num - 1, cnt + 1, str + " "+ (num - 1) );
    }
    
   
}