[알고리즘_풀이] 백준 - 1로 만들기 java

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

1463번: 1로 만들기

BottomUp

: 2->1, 3->1, 4->1, ... , 결국 N->1 를 계산하는 방식으로 풀었다.

import java.util.*;

public class Main {

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

}

 

TopDown

import java.util.*;

public class Main {
	static int[] dp;
	// top-down
	public static int memoization(int targetNum) {
		if(targetNum == 1) return 0;
		if(dp[targetNum] >= 0) {
			return dp[targetNum];
		}
		
		int tmp = memoization(targetNum-1);
		
		if(targetNum%2 == 0) tmp = Math.min(tmp, memoization(targetNum/2));
		if(targetNum%3 == 0) tmp = Math.min(tmp, memoization(targetNum/3));

		dp[targetNum] = tmp + 1;
		
		return dp[targetNum];
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		dp = new int[N+1];
		Arrays.fill(dp, -1);
		
		System.out.println(memoization(N));
	}

}