백준 1463 1로 만들기

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 N이 주어졌을 때 3가지 연산을 최소로 사용하여 1을 만드는 횟수를 찾는 문제입니다.

 

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

저는 이문제를 바텀 업 방식으로 해결하였습니다. 우선은 N이 1일때는 0입니다. 

 

 N이 2일때부터 반복문을 돌리는데 N이 만약 2로 나누어 떨어진다면 이때 횟수는 dp[N-1] + 1 과 dp[N/2] + 1 중 더 작은값이 될 것입니다.

 

N이 3일때는 마찬가지로 dp[N-1] + 1 과 dp[N/3] + 1 중 더 작은값이 될 것입니다.

 

저는 처음에 if(i % 2 == 0) 

else if(i % 3 ==0)  과 같이 코드를 작성했는데 틀려서 고민을 해보니 2와 3의 배수인 6의 배수인 경우 두경우 모두를 봐줘야 하므로

따로따로 if문을 작성해 주어야 했습니다.

이점을 주의해 주시면 크게 어려운 점은 없습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int *dp = new int[1000001];
	fill_n(dp, 1000001, 0);
	int N; cin >> N;
	dp[1] = 0;
	
	for(int i = 2; i <= N; i++) {
		dp[i] = dp[i-1] + 1;
		if(i % 2 == 0)
			dp[i] = min(dp[i-1] + 1, dp[i/2] + 1);
		
		if(i % 3 == 0)
			dp[i] = min(dp[i-1] + 1, dp [i/3] + 1);
		
	}
	cout << dp[N];
	return 0;
}