05.01. 1로 만들기 [Dynamic Programming][백준 1463]

https://www.acmicpc.net/problem/1463

 

1463번: 1로 만들기

 

Algorithm classification : Dynamic Programming

05.01.1. Problem

There are three operations that can be used for integer X as follows.

• If X is divisible by 3, divide by 3.
• If X is divisible by 2, divide by 2.
• subtract 1

Given an integer N, we try to make 1 by appropriately using the above three operations. Print the minimum number of times an operation is used.

 

05.01.2. Input limit

The first line is given an integer N greater than or equal to 1 and less than or equal to 10^6.

 

05.01.3. Output

In the first line, the minimum value of the number of operations is printed.

 

05.01.4. Solution

N을 1로 만드는 최소 횟수는

점화식으로 표현할 수 있습니다.

int dp[1000001] = {0};

int cal(int n){
	if(n == 1) return 0;
	if(dp[n] != 0) return dp[n];
	
	int result = cal(n-1) + 1;
	if(n%3 == 0) result = min(result, cal(n/3) + 1);
	if(n%2 == 0) result = min(result, cal(n/2) + 1);
	dp[n]= result;
	return result;
}

Top-down 방식이고 Bottom-up으로도 구현할 수 있습니다.

	for(int i = 1; i < N; i++){
        dp[i+1] = min(dp[i+1], dp[i]+1);
        if(i*2 <= N) dp[i*2] = min(dp[i*2], dp[i]+1);
        if(i*3 <= N) dp[i*3] = min(dp[i*3], dp[i]+1);
    }

 

 

2021.12.15 - [학부공부/Algorithm_알고리즘] - 09. Dynamic Programming(1)

09. Dynamic Programming(1)

2021.12.17 - [학부공부/Algorithm_알고리즘] - 10. Dynamic Programming(2)

10. Dynamic Programming(2)

에서 소개해드린 피보나치 수열 예제와 비교해보면 점화식만 살짝 upgrade된 버전의 문제이니 한번 직접 풀어보시는 것을 추천드립니다.