[ Baekjoon ] #1463 1로 만들기

[Baekjoon][https://www.acmicpc.net/problem/1463]

 

다이나믹 프로그래밍(DP) > Bottom-up 형식

풀이)

 (1) d[n] : 1 ~ N 일때 1로 만들기 위한 최소 개수를 저장.

 (2) 가장 작은 단위인 dp[1] = 0 으로 초기화 하여, dp[2] 부터 For문 처리 (Bottom-up) 형식

 (3) Math.min() 함수로 메모이제이션 해두었던 값과 현재 값의 최소값을 비교하여,

     연산을 사용하는 횟수의 최솟값을 구한다.

 

import java.util.Scanner;

public class baekjoon_1463 {
	static int[] dp;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		dp = new int[1000001];
		dp[1] = 0;
		
		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]);
	}
}