1로 만들기

문제

1로 만들기

풀이

를 로 만드는 데 필요한 최소 횟수를 라 합시다. 그렇다면 아래 점화식을 통해 답을 구할 수 있습니다.

단, 나누기는 나누어 떨어지는 경우에만 고려해야 합니다.

을 빼는 것만으로도 로 만들 수 있으므로 의 최댓값은 이고, 따라서 int 자료형으로 풀 수 있습니다.

코드

Python

n = int(input())
 
dp = [0] * (n + 1)
 
for i in range(2, n + 1):
    dp[i] = dp[i - 1] + 1
 
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)
 
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)
 
print(dp[n])

C++

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
    vector<int> dp(n + 1);
 
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + 1;
 
        if (i % 2 == 0)
            dp[i] = min(dp[i], dp[i / 2] + 1);
 
        if (i % 3 == 0)
            dp[i] = min(dp[i], dp[i / 3] + 1);
    }
 
    cout << dp[n];
 
    return 0;
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
        int dp[] = new int[n + 1];
 
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
 
            if (i % 2 == 0)
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
 
            if (i % 3 == 0)
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
        }
 
        bw.write(dp[n] + "");
 
        bw.close();
    }
}