[백준] 1463: 1로 만들기

 

 

 

입출력 예제이다.

 

 

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

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

        for (int i = 2; i <= N; i++) {
            // 1을 빼는 경우
            dp[i] = dp[i - 1] + 1;

            // 2로 나누어 떨어지는 경우
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }

            // 3으로 나누어 떨어지는 경우
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }

        System.out.println(dp[N]);
    }
}

 

 

주어진 정수 N을 1로 만들기 위한 최소 연산 횟수를 계산하도록 작성했다.

Bottom-Up 방식의 다이나믹 프로그래밍을 사용했다. 

먼저 입력으로 받은 정수 N까지의 최소 연산 횟수를 저장하기 위한 배열 dp를 선언하고 초기화한다.

2부터 N까지 반복하면서 각 숫자에 대한 최소 연산 횟수를 계산한다.
   - 현재 수에서 1을 뺀 경우(dp[i - 1] + 1): 1을 뺀 수의 최소 연산 횟수에 1을 더한다.
   - 현재 수를 2로 나눌 수 있는 경우(i % 2 == 0): 2로 나눈 수의 최소 연산 횟수에 1을 더한 값과 현재 수에서 1을 뺀 경우 중 더 작은 값을 선택한다.
   - 현재 수를 3으로 나눌 수 있는 경우(i % 3 == 0): 3으로 나눈 수의 최소 연산 횟수에 1을 더한 값과 현재 수에서 1을 뺀 경우 중 더 작은 값을 선택한다.

그러면 배열 dp[N]에는 최종적으로 1을 만들기 위한 최소 연산 횟수가 저장되어 있을 것이다.

그 후 마지막으로 최소 연산 횟수를 출력한다.