1로 만들기

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

1463번: 1로 만들기

 

import java.util.*;

class Main {
    public static int[] cache = new int[1000001];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < cache.length; i++) {
            cache[i] = -1;
        }
        int n = sc.nextInt();
        System.out.println(recursive(n));
    }
    
    public static int recursive(int n) {
        if (n == 2 || n == 3) {
            return 1;
        }
        if (n == 1) {
            return 0;
        }
        if (cache[n] != -1) {
            return cache[n];
        }
        int num = Integer.MAX_VALUE;
        if (n % 3 == 0) {
            num = 1 + recursive(n / 3);
        }
        if (n % 2 == 0) {
            num = Math.min(num, 1 + recursive(n/2));
        }
        if (n > 1) {
            num = Math.min(num, 1 + recursive(n -1));
        }
        return cache[n] = num;
    }
}

최소값을 만들어야하기 때문에 재귀적으로 탈출조건을 만들어둔다. 

해당하는 조건을 만족하지 못하면 +1을 한다.