Problem Description

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

  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
  • 첫째 줄에 1보다 크거나 같고, 10^6^보다 작거나 같은 정수 N이 주어진다
  • 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

백준에서 알고리즘 문제집중에서 DP(Dynamic Programming)에 관련된 문제만 모아놓은 문제집이 있는데 이문제도 DP관련된 문제이다. 빠른시일내에 DP에 관한 글도 포스팅할 예정이다.

정수 N을 입력받고 그 정수에 사용할수 있는 연산 세가지를 사용하여 연산을 사용하는 최솟값을 출력하는 것이다.

DP문제는 점화식을 찾으면 쉽게 풀수 있다고 한다. 이해를 위해 직접 1부터 10까지의 연산의 최솟값을 적어보았다.

baekjoon1463

배열로 보면 DP[10]의 값이 3이므로 10이 1로 될 때까지 진행하는 연산은 3번이다(10 -> 9 -> 3 -> 1).

한번 무식하게 계산해보면 규칙이 보인다.

  • 1을 뺄때는 DP[i] = DP[i-1] + 1
  • 2로 나눌 수 있을 때는 DP[i] = DP[i/2] + 1
  • 3으로 나눌 수 있을 때는 DP[i] = DP[i/3] + 1

머리아픈 일은 다 해결했다. 이제 쉽게쉽게 코딩해보자.

Code block

A Java Example:

import java.util.Arrays;
import java.util.Scanner;

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

		int N = sc.nextInt();

		DP = new int[N+1];

		DP[1] = 0;
		for (int i = 2; i < N+1; i++)
		{
			DP[i] = DP[i-1]+1;
			if (i % 2 == 0 && DP[i] > DP[i/2]+1)
			{
				DP[i] = DP[i/2]+1;
			}
			if (i % 3 == 0 && DP[i] > DP[i/3]+1)
			{
				DP[i] = DP[i/3]+1;
			}
		}
		System.out.println(DP[N]);
	}
}