[Java] 1463 1로 만들기

문제

문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 
연산을 사용하는 횟수의 최솟값을 출력하시오.

입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1 
2
예제 출력 1 
1

예제 입력 2 
10
예제 출력 2 
3

힌트
10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

문제 풀이

경우의 수를 모두 확인하면서 그 최소 값을 찾았다.

입력받은 N부터 3으로 나누어 떨어지면 /3 한 값을 재귀, 2로 나누어 떨어지면 /2한 값을 재귀해 나가고 안되면 -1한 값으로 재귀를 이어나가는 형태로 진행한다.

이때 num가 1이 되면 현재까지 기록된 최솟값과 비교하여 갱신하고 종료한다.

이때 중요한 점은 모든 값을 다 찾으려고 하면 시간초과에 걸릴 수 있다.

현재까지의 최솟값보다 횟수가 커지면 거기서 멈춰주는 작업이 필요하다. 

자바 코드

import java.util.Scanner;

public class MakeOne {
    private static int N;
    private static int cnt = Integer.MAX_VALUE;
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();

        calcul(N, 0);

        System.out.println(cnt);
    }

    private static void calcul(int num, int depth){
    	// 만약 계산중인 횟수가 현재까지의 최솟값보다 크다면 미리 종료한다.
        if(depth > cnt)
            return;

		// 숫자가 1이 됬을 때 현재까지의 최솟값과 비교하여 더 낮은 값으로 갱신하고 종료.
        if(num == 1){
            cnt = Math.min(cnt, depth);
            return;
        }

		// 3으로 나눴을 때 딱 떨어지면 3으로 나눈 수로 재귀
        if(num % 3 == 0)
            calcul(num / 3, depth + 1);
            
      	// 2으로 나눴을 때 딱 떨어지면 2으로 나눈 수로 재귀
        if(num % 2 == 0)
            calcul(num / 2, depth + 1);
		
        // 기본은 -1 한 값으로 재귀
        calcul(num - 1, depth + 1);
    }
}