[백준 1463] 1로 만들기

 

주어진 수 n이 3의 배수이면 나누기 3, 2의 배수이면 나누기 2, 그 외 일때는 1을 뺀다.

한번 연산을 수행했을때마다 /3, /2, -1 중에서 가장 1이 빨리 될 경우를 찾아서 연산한다.

제한시간이 2초이므로 메모이제이션 기법을 사용하였다.

 

 

 

1. 동적배열을 만들어 나올 수 없는 수로 초기화 한 후, 각 수 마다 최선의 횟수를 배열에 담는다.

2. n 이 1일때는 예외처리한다.

3. n 이 1일때 0 을 리턴하는 것으로 처리하였으므로 나머지 경우엔 연산을 +1 한다.

 

	public static ArrayList<Integer> dp = new ArrayList<Integer>();
	
	public static int makeOne(int n) {
		if(n == 1) return 0;
		if(dp.get(n) != -1) return dp.get(n);
		
		int result = makeOne(n-1) + 1;
		if(n%3 == 0) {
			int divide3 = makeOne(n/3) + 1;
			result = result < divide3 ? result : divide3;
		}
		if(n%2 == 0) {
			int divide2 = makeOne(n/2) + 1;
			result = result < divide2 ? result : divide2;
		}
		dp.set(n, result);
		return result;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();

		for(int i=0; i<n+1; i++)
			dp.add(-1);
		System.out.println(makeOne(n));
	}