[BOJ][1463] 1로 만들기

1. 문제 링크

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

2. 사용 알고리즘

DP

3. 풀이

d[n] : n을 1로 만들기 위한 연산 횟수의 최소값

• n / 3을 1로 만들기 위한 연산 횟수의 최소값 : d[n / 3]

• n / 2를 1로 만들기 위한 연산 횟수의 최소값 : d[n / 2]

• n - 1을 1로 만들기 위한 연산 횟수의 최소값 : d[n - 1]

• n / 3, n / 2, n - 1을 수행하기 위한 연산 횟수 1회

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

4. 소스 코드

4-1. C++

4-1-1. Top-Down

https://github.com/dev-aiden/problem-solving/blob/main/boj/1463.cpp

#include <iostream>

using namespace std;

int d[1000003];

int op(int num) {
    if (num == 1) return 0;
    if (d[num] > 0) return d[num];
    d[num] = op(num - 1) + 1;
    if (num % 2 == 0) {
        int temp = op(num / 2) + 1;
        if (d[num] > temp) d[num] = temp;
    }
    if (num % 3 == 0) {
        int temp = op(num / 3) + 1;
        if (d[num] > temp) d[num] = temp;
    }
    return d[num];
}

int main(void) {
    ios_base::sync_with_stdio(false);
    int n; cin >> n;
    cout << op(n) << "\n";
    return 0;
}

4-1-2. Bottom-Up

https://github.com/dev-aiden/problem-solving/blob/main/boj/1463_2.cpp

#include <iostream>

using namespace std;

int d[1000003];

int main(void) {
    ios_base::sync_with_stdio(false);
    int n; cin >> n;
    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;
    }
    cout << d[n] << "\n";
    return 0;
}

4-2. JAVA

4-2-1. Top-Down

https://github.com/dev-aiden/problem-solving/blob/main/boj/1463.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int[] d = new int[1000003];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.println(op(n));
    }

    public static int op(int num) {
        if(num == 1) return 0;
        if(d[num] > 0) return d[num];
        d[num] = op(num - 1) + 1;
        if(num % 2 == 0) {
            int temp = op(num / 2) + 1;
            if(d[num] > temp) d[num] = temp;
        }
        if(num % 3 == 0) {
            int temp = op(num / 3) + 1;
            if(d[num] > temp) d[num] = temp;
        }
        return d[num];
    }
}

4-2-2. Bottom-Up

https://github.com/dev-aiden/problem-solving/blob/main/boj/1463_2.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int[] d = new int[1000003];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        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]);
    }
}