문제 출처

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

문제 설명

정수 N이 주어질 때,
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
X - 1을 한다.
의 3가지 연산을 이용하여 1을 만들 때, 연산을 사용하는 횟수의 최솟값을 출력하라.

접근 방법

간단한 반복문으로도 풀 수 있지만, DP를 이용하여 Bottom-Up 방식을 이용한다.
dp[1]은 0으로 초기화 한 뒤,
dp[N]이 될 때까지, i 2 한 경우, i 3 한 경우, i + 1한 경우 중 횟수가 가장 작은 경우를 dp[i]로 설정한다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        
        int[] dp = new int[N+1];
        
        dp[1] = 0;
        
        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);
            }
        }
        System.out.println(dp[N]);
    }
}

Review

import java.util.*;

public class BOJ_9_1463_1로_만들기_reivew {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int sc = scanner.nextInt();

        int max = Integer.MAX_VALUE;

        int[] dp = new int[sc+1];

        for(int i = 0; i<dp.length; i++){
            dp[i] = max;
        }
        dp[sc] = 0;

        for(int i = sc; i>1; i--){
            if(i%3 == 0) dp[i/3] = Math.min(dp[i/3], dp[i] +1);
            if(i%2 == 0) dp[i/2] = Math.min(dp[i/2], dp[i] +1);
            dp[i-1] = Math.min(dp[i-1], dp[i] +1);
        }
        System.out.println(dp[1]);
    }
}

알게된 점

Bottom-up 방식으로 dp[2]부터 점차 dp[N]까지 접근하는 방식을 사용했다.

문제푼 흔적

Reivew