문제

입력

출력

예제

힌트

idea

이번 문제는 dp(다이나믹 프로그래밍)을 사용하는 문제이다.
이 알고리즘에 대해 배운적이 없기 때문에 인터넷을 이용하여 미리 공부하고 시작하였다.
dp 즉, 동적계획법은 가능할 수 있는 모든 경우의 수를 찾아주기에 결과에 대해서는 확실성을 보장할 수 있다. 모든 경우를 고려해야 하는 점을 보완한 것이 그리디 알고리즘이만 그리디는 최적을 찾지 못하는 경우도 있다.

dp는 단계적인 특성을 나타낸다.
예를 들어, 피보나치 수열을 구하는 함수는 다음과 같다.

function fib(n)
 if n = 0
  return 0
 else if n=1
  return 1
 else
  return fib(n-1) + fib(n-2)

이때, f(5)를 구한다고 가정하자.

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

다음과 같이 계산이 중복되는 부분이 있음을 확인할 수 있으며 이로 인해 계산 속도가 떨어지게 된다.
그것을 방지하기 위해 계산한 값을 저장하도록 하는 방식을 사용한다.

다시 문제로 넘어와서,
문제를 보면 경우의 수는 세가지 경우가 있다.
첫번째, X를 3으로 나누기. 두번째, X를 2로 나누기. 마지막 1을 빼기.
우리는 계산 과정을 몇번을 거쳤는지를 계산해야하기 때문에
첫번째는 [X/3]+1, 두번째는 [X/2]+1, 마지막은 [X-1]+1의 값을 가지게 된다

그 후 원하는 값을 저장하기 위해서는 아래에서 부터 차곡차곡 쌓아 올라가 원하는 수까지 도달해야한다.

1의 값을 원하기 때문에 X가 1일 경우 계산과정을 거치지 않으므로 0이된다. (x[1]=0)
그 후 원하는 값까지 차곡차곡 쌓아 올린다.
X가 2일 경우 x[2]는 연산 1과 3을 사용하는데 둘 중 최소값을 사용한다. 1번 일때는 x[2-1] + 1, 3번은 x[2/2] + 1. 둘 다 값이 1 이므로 x[2]=1을 저장한다.
이와 같이 아래에서부터 쌓아올리면 값이 나온다.

이번 알고리즘 같은 경우에는 내가 알지 못했던 것이고 문제를 푸는 과정에서 찾아본 것이 많았기 때문에 평소보다 자세히 적었다.

정리

첫번째, X를 3으로 나누기. 두번째, X를 2로 나누기. 마지막 1을 빼기.
우리는 계산 과정을 몇번을 거쳤는지를 계산해야하기 때문에
첫번째는 [X/3]+1, 두번째는 [X/2]+1, 마지막은 [X-1]+1의 값을 가지게 된다.

아래에서부터 값을 쌓아 올리는데 만약 조건이 여러개가 동시에 맞는다면 그 중 최소값을 갖게 된다.

Code

import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int X;
		
		X=in.nextInt();
		
		int x[] = new int[X+1];
		x[1]=0;
		for (int i=2;i<=X;i++) {
			
			x[i]=x[i-1]+1;	
			if(i%3==0)
				x[i]=Math.min(x[i],x[i/3]+1);
			if(i%2==0)
				x[i]=Math.min(x[i],x[i/2]+1);
		}
		System.out.println(x[X]);
	}
}

결과