[DP]문제#10. 1로 만들기

1463번: 1로 만들기 (acmicpc.net)

d[i]를 저렇게 먼저 초기화시킬 수 있겠구나!

 

import java.util.Scanner;

//1로 만들기
public class Making1 {

	static int n;
	static int[] d;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in=new Scanner(System.in);
		n=in.nextInt();	
		d=new int[n+1];
		
		d[1]=0;
		for(int i=2;i<=n;i++) {
				d[i]=d[i-1]+1;
				if(i%3==0) 
					d[i]=Math.min(d[i], d[i/3]+1);
				if(i%2==0)
					d[i]=Math.min(d[i], d[i/2]+1);
		}
		System.out.println(d[n]);
	}
}