링크

1로 만들기

문제

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

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

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

입력

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

출력

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

풀이

DP문제를 푸니까 DP는 항상 점화식과 규칙을 찾을려고 시간을 조금 할애해야한다는 것을 깨달았다.

각각의 DP의 경우의 수를 12정도까지 구하니깐 어느 정도 규칙까지는 보였는데 그걸 점화식으로 나타낼려고 하니까 조금 어려운듯...ㅎㅎ

그렇기에 각각의 최소값을 비교해준다. 어떤 뜻이냐면
DP[0]=0, DP[1]=0, DP[2]=1, DP[3]=1, DP[4]=2, DP[5]=3, DP[6]=2, DP[7]=3, DP[8]=3, DP[9]=2, DP[10]=3 ...
대충 10까지 일단 경우의 수를 구해본다.

그리고

이 힌트에서 생각해볼수 있는게
10은 2로 나누어 떨어진다면 10 -> 5 -> 4 ->2-> 1 이 경우엔 4
하지만 10의 최소값은 10 -> 9 -> 3 -> 1 이 경우엔 3이 된다.

또 하나의 수를 따져주자면 2와 3의 배수인 DP[12]를 따져보자
그러면 위처럼 DP[12]+DP[11]+1(1을 빼주는 경우 +)를 따져줘볼 수가 있고 DP[12/3]+1(3을 한번 더 나눠주니 +), DP[12/2]+1(2를 한번더 나눠주니 +)를 따져줘볼 수가 있다. 우리는 차후 수가 넘어갔을 때
어떤 값이 최소값이 될 수 있을지 모른다. 그렇기에 이제 각각의 최소 값을 다 따져주는 것이다.

Code

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

public class Main {
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		int n=Integer.parseInt(br.readLine());
		int dp[]=new int[1000001];
		dp[0]=0;
		dp[1]=0;
		dp[2]=1;
		dp[3]=1;
		
		for(int i=4; i<=n; i++)
		{
			dp[i]=dp[i-1]+1;
			
			if(i%3==0)
				dp[i]=Math.min(dp[i], dp[i/3]+1);
			if(i%2==0)
				dp[i]=Math.min(dp[i], dp[i/2]+1);
		}
		
		System.out.println(dp[n]);
    }
}