[백준] 1463 - 1로 만들기 (자바/Java) : DP

문제 링크

성능 요약

메모리: 55224 KB, 시간: 224 ms

분류

다이나믹 프로그래밍(dp)

문제 설명

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 10⁶보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

정수 X가 2와 3 모두 나누어 떨어지지 않는 경우에는 X-1을 하면 된다.

 

문제는 2 또는 3과 나누어 떨어지는 경우에, 2나 3으로 나누는 것이 최적의 답이 아닐 수 있다는 점이다.

 

예를 들어, X가 28일 때

먼저 2로 나누면

28 14 7 6 3 1 로 6번이 소요된다.

 

그러나 1로 빼면

28 27 9 3 1 로 5번의 연산이면 가능하다.

이처럼 1로 뺀 것과 2 또는 3으로 나누는 것 중 최소값을 찾아야 한다.

이를 위해 dp의 top-down 방식을 활용했다.

경우의 수는 4가지로 나눌 수 있다.

함수명: find(n)

1. 2와 3 모두 나누어 떨어지는 경우

$$ dp[n] = min(find(n/3), find(n/2), find(n-1)) +1 $$

2. 2로 나누어 떨어지는 경우

$$ dp[n] = min(find(n/2), find(n-1)) +1 $$

3. 3으로 나누어 떨어지는 경우

$$ dp[n] = min(find(n/3), find(n-1)) +1 $$

4. 2와 3 모두 나누어 떨어지지 않는 경우

$$ dp[n] = find(n-1) +1 $$

이를 바탕으로 작성한 코드는 다음과 같다.

 

import java.util.Scanner;

public class Main {
	static int N;
	static int[] dp = new int[1000001];

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		dp[1] = 0;
		System.out.println(find(N));
	}

	static int find(int num) {
		if (num == 1)
			return 0;

		if (dp[num] != 0)
			return dp[num];

		if (num % 2 == 0 && num % 3 == 0) {
			dp[num] = Math.min(find(num / 2), find(num / 3)) + 1;
			dp[num] = Math.min(dp[num], find(num - 1));
		} else if (num % 2 == 0)
			dp[num] = Math.min(find(num / 2), find(num - 1)) + 1;
		else if (num % 3 == 0)
			dp[num] = Math.min(find(num / 3), find(num - 1)) + 1;
		else
			dp[num] = find(num - 1) + 1;

		return dp[num];
	}
}