1로 만들기

풀이

 이 문제는 전형적인 다이나믹 프로그래밍 문제다. X = 10인 경우, 10 -> 9 -> 3 -> 1 과정을 거쳐 1이 되는데, 9의 경우에는 9 -> 3 -> 1의 과정을 거치며, 3의 경우에는 3 -> 1의 과정을 거친다. 즉, 10을 구할 때 이전의 결과인 9의 결과를, 9를 구할 때는 3의 결과를 이용하는 문제다. 나는 아래와 같이 바텀업 방식으로 구현했다.

시간 복잡도 : O(N)
💡 Java 풀이입니다. Python 풀이와 다를 수 있습니다.

Java

import java.io.*;
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(String.valueOf(dp[N]));

        bw.flush();
        bw.close();
        br.close();
    }
}

Python

n = int(input())

data = [0 for _ in range(n+1)]

for i in range(2, n+1):
    data[i] = data[i-1] + 1
    if i % 3 == 0:
        data[i] = min(data[i//3] + 1, data[i])
    if i % 2 ==0:
        data[i] = min(data[i//2] + 1, data[i])

print(data[n])