[Java] 백준 1463 1로 만들기

 

문제

정수 N이 주어졌을 때, 3 종류의 연산을 적절히 사용해 1을 만드려고 한다.

정수 N을 1로 만드는 연산횟수의 최솟값을 출력해라.

- 1 <= N의 범위 <= 10^6

- 1)  X /= 3

- 2)  X /= 2

- 3)  X -= 1

 

풀이

연산 순서에 따라서 결과가 달라지고, 연산 횟수의 최솟값을 구하는 문제이므로 모든 경우의 수를 따져야 한다.

즉, 다이나믹 프로그래밍을 사용해서 풀이해야 한다.

- 숫자를 1부터 X까지 증가시키며 최소 연산 횟수를 담는 dp 배열을 만들어나간다. 

- 3가지 연산 조건에 맞는지 확인하며 가장 작은 값으로 dp배열을 초기화한다.

 

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int X = Integer.parseInt(br.readLine());
        int[] dp = new int[1000001];
        for (int i = 2; i <= X; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        // 모든 조건을 비교하여 최소값으로 dp[i]방을 초기화한다. 
        for (int i = 2; i <= X; i++) {
            if (i % 3 == 0 && dp[i / 3] + 1 < dp[i]) // 3으로 나눠질 경우 : 3으로 나눈 값의 최소 연산 + 1한 값으로 초기화
                dp[i] = dp[i / 3] + 1;
            if (i % 2 == 0 && dp[i / 2] + 1 < dp[i]) // 2로 나눠질 경우 : 2로 나눈 값의 최소 연산 + 1한 값으로 초기화
                dp[i] = dp[i / 2] + 1;
            if (dp[i - 1] + 1 < dp[i]) // 1로 나눠질 경우 : -1한 값의 최소 연산 + 1한 값으로 초기화
                dp[i] = dp[i - 1] + 1;
        }

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