1463. 1로 만들기

1463. 1로 만들기

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

---

동전 경우의 수 구하는 문제랑 비슷하다. 다만 앞에서 하는게 아니라 뒤에서 풀어야 풀린다. (다른 방법은 잘 모르겠음)

예를 들어서 8이 주어지면 8에서 만들 수 있는 수는 8-1, 8/2 두 가지이다. 이 때 나오는 수인 7, 4를 인덱스로 가지는 dp 에 1을 넣어준다. 이것이 맨 처음에 1을 넣어주는 부분이다. (초기화를 n-1하는 이유는 어떤 수 n에서 1을 만드는 가장 최댓값이 n-1이기 때문이다.)

그리고 그 다음 7부터 거꾸로 dp를 만들어 주면 된다. (인덱스) i에서 i/2, i/3, i-1에 i를 만들수 있는 값 + 1과 해당 값의 최솟값만 갱신해 주고, 목표가 1을 만드는 것이기 때문에 dp의 1번째를 리턴해주면 된다.

import java.util.Scanner;

public class Main {

    public int problem1464(int n) {
        int[] dp = new int[n];

        if (n == 1) {
            return 0;
        }

        for (int i = 0; i < n; ++i) {
            dp[i] = n-1;
        }

        if (n - 1 >= 0) {
            dp[n - 1] = 1;
        }
        if (n % 2 == 0) {
            dp[n / 2] = 1;
        }
        if (n % 3 == 0) {
            dp[n / 3] = 1;
        }

        for (int i = n - 1; i > 0; --i) {
            dp[i - 1] = Math.min(dp[i] + 1, dp[i - 1]);
            if (i % 2 == 0) {
                dp[i / 2] = Math.min(dp[i] + 1, dp[i / 2]);
            }
            if (i % 3 == 0) {
                dp[i / 3] = Math.min(dp[i] + 1, dp[i / 3]);
            }
        }
        return dp[1];
    }

    public static void main(String[] args) {
        // Use the Scanner class
        Main sol = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(sol.problem1464(n));
    }
}