[백준 1463번] 1로 만들기

문제 링크: 1463번 1로 만들기

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

 

예를들어, 9는 '27을 3으로 나눈다'는 한 번의 수행 또는 '10에서 1을 뺀다'는 한 번의 수행을 통해 만들어진다. 이를 통해 점화식을 세우면 다음과 같다.

a[n] = min(a[n/3], a[n/2], a[n-1]) + 1

다만 a[n/3]과 a[n/2]는 나누어떨어지지 않는 경우 구할 수 없기에 divBy3, divBy2를 미리 선언하여 i가 3 또는 2로 나누어떨어지지 않을 경우 최댓값을 저장하도록 하여 min()에서 고려되지 않도록 한다.

 

import java.util.Scanner;
import java.util.Arrays;

class Main {
    static int[] arr;

    public static int min(int a, int b, int c) {
        int[] temp = {a, b, c};
        Arrays.sort(temp);
        return temp[0];
    }

    public static int min(int a, int b) {
        if (a <= b) return a;
        return b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        arr = new int[n+3];

        arr[2] = arr[3] = 1;
        for (int i = 4; i <= n; i++) {
            int divBy3 = i%3==0 ? arr[i/3] : Integer.MAX_VALUE;
            int divBy2 = i%2==0 ? arr[i/2] : Integer.MAX_VALUE;
            arr[i] = min(divBy3, divBy2, arr[i-1]) + 1;
        }

        int answer = arr[n];
        System.out.println(answer);

        sc.close();
    }
}