21.07.06 - [BOJ] 1463. 1로 만들기

[suhyunsim]

문제

• 1463

핵심 아이디어

• 3으로 나누는 것 -> 2로 나누는 것 -> 1을 빼는 것 우선순위(그게 수를 더 작아지게 하니까) => 반례(10)가 있어서 사용 못함!
• DP

어려운 점, 실수

풀이

재귀로 풀이 (Top Down)

package main.java.com.poogle.BOJ.Q1463;

import java.util.Scanner;

public class Main {
    static int[] d;
    public static int go(int n) {
        if (n == 1) return 0;
        if (d[n] > 0) return d[n];
        d[n] = go(n - 1) + 1;
        if (n % 2 == 0) {
            int tmp = go(n / 2) + 1;
            if (d[n] > tmp) d[n] = tmp;
        }
        if (n % 2 == 0) {
            int tmp = go(n / 3) + 1;
            if (d[n] > tmp) d[n] = tmp;
        }
        return d[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        d = new int[n + 1];
        System.out.println(go(n));
    }
}

Bottom up

package main.java.com.poogle.BOJ.Q1463;

import java.util.Scanner;

public class Main {
    static int[] d;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        d = new int[n + 1];
        d[1] = 0;
        for (int i = 2; i <= n; i++) {
            d[i] = d[i - 1] + 1;
            if (i % 2 == 0 & d[i] > d[i / 2] + 1) {
                d[i] = d[i / 2] + 1;
            }
            if (i % 3 == 0 & d[i] > d[i / 3] + 1) {
                d[i] = d[i / 3] + 1;
            }
        }
        System.out.println(d[n]);
    }
}