BOJ 1463. 1로만들기

BOJ 1463. 1로 만들기

풀이

d[n]= 1로 만드는 연산을 하는 최솟값

점화식
d[n] = min(d[n-1] +1 , d[n2] + 1, d[n3] + 1 ) 

대략적인 논리로, 그대로 쓰지는 않고
2나 3으로 나누어 떨어지는지 확인 조건문으로 처리 필요

Bottom-Up

입력이 1일때는 어떠한 연산도 할 필요가 없으므로
d[1]에 0을 넣어 시작한다.

import java.io.*;
import java.util.Scanner;

class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int[] d = new int[10000001];
        int n = sc.nextInt();

        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]);
        sc.close();
    }
}

fun main() {
    val d = IntArray(1000001) { 0 }
    val n = readLine()!!.toInt()

    d[1] = 0
    (2..n).forEach { 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
        }
    }

    println(d[n])
}

Top-Down

import java.util.Scanner;

class Main {
    static int[] d = new int[1000001];

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

    static int go(int i) {
        if (i == 1) return 0;
        if (d[i] > 0) return d[i];

        d[i] = go(i - 1) + 1;

        if (i % 2 == 0) {
            int temp = go(i / 2) + 1;
            if (d[i] > temp) d[i] = temp;
        }

        if (i % 3 == 0) {
            int temp = go(i / 3) + 1;
            if (d[i] > temp) d[i] = temp;
        }
        return d[i];
    }
}

val d = IntArray(1000001) { 0 }

fun main() {
    println(go(readLine()!!.toInt()))
}

fun go(i: Int): Int {
    if (i == 1) return 0
    if (d[i] > 0) return d[i]

    d[i] = go(i - 1) + 1
    if (i % 2 == 0) (go(i / 2) + 1).let { if (d[i] > it) d[i] = it }
    if (i % 3 == 0) (go(i / 3) + 1).let { if (d[i] > it) d[i] = it }

    return d[i]
}

풀이소스

github.com/beomjo/algorithm-study/blob/main/BOJ/java/1463.java github.com/beomjo/algorithm-study/blob/main/BOJ/kotlin/1463.kt