dp 백준 1463 1로 만들기

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

1463번: 1로 만들기

1로 만들기

입력 된 숫자를 1로 만드는 최소한의 방법을 구하는 문제이다.

 

방법은 

1. 3로 나누어 진다면 3으로 나누기

2. 2로 나누어 진다면 2로 나누기

3. 둘다 아니라면 1 빼기 

 

이 문제는 dp를 활용하여 해결했으며 각 숫자별 점화식을 구해야한다. 

 

숫자 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
방법 0 1 1 2 3 2 3 4 ........

 

이렇게 쭉 적다보면 몇 가지 규칙을 발견할 수 있다. 

 

3으로 나누어질 때는 이전 3으로 나누어 지는 방법에 + 1과 같다는 점 

[i/3] + 1

 

2로 나누어 질때는 이전 2로 나누어 지는 방법에 + 1과 같다는 점 

[i/2] + 1 

 

그리고 위 둘다 아니면 이전 단계에서 1을 더해준 것과 같다는 점이다. 

[i-1] + 1

 

그런데 3으로 나누어질 때와 2로 나누어 질 때 주의할 점이 있다. 과연 [i-1] + 1이 [i/3] + 1과 [i/2] + 1 보다 무조건 작다는 점을 확신할 수 있냐는 점이다!! 그래서 3으로 나누어 질때와 2로 나누어 질때 [i-1] + 1, [i/3] + 1,  [i/2] + 1 가장 작은 값을 넣어야한다. 

 

10인 경우 2로 가장 먼저 나누어지지만 2로 나누어 질때보다 -1을 한 후 해결하는 방법이 더 효율적이다. 

 

		if(i%3==0){
			if(i%2==0)
				dp[i] = min(min(dp[i/2] + 1, dp[i/3] + 1), dp[i-1] + 1);
			else
				dp[i] = min(dp[i-1] + 1, dp[i/3] + 1);
		}else if(i%2==0)
			dp[i] = min(dp[i-1] + 1,dp[i/2] + 1); 
		else
			dp[i] = dp[i-1] + 1;

#include <cstdio>
#include <algorithm>

using namespace std;

int N;
int count = 0;
int dp[1000002];
int main(){
	scanf("%d", &N);
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	for(int i = 4; i <= N; i++){
		if(i%3==0){
			if(i%2==0)
				dp[i] = min(min(dp[i/2] + 1, dp[i/3] + 1), dp[i-1] + 1);
			else
				dp[i] = min(dp[i-1] + 1, dp[i/3] + 1);
		}else if(i%2==0){
			dp[i] = min(dp[i-1] + 1,dp[i/2] + 1); 
		}else{
			dp[i] = dp[i-1] + 1;
		}
	}
	printf("%d", dp[N]);
}