[BOJ] 백준 1463번: 1로 만들기

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

1463번: 1로 만들기

기본적인 DP 예제입니다.

 

1) bottom-up 풀이

#include <bits/stdc++.h>
using namespace std;

int N, dp[1000001];

void solve(){
	dp[1] = 0;
	for(int i = 2; i <= N; ++i){
		dp[i] = dp[i-1] + 1;
		if(i % 3 == 0 && dp[i] > dp[i/3] + 1) dp[i] = dp[i/3] + 1;
		if(i % 2 == 0 && dp[i] > dp[i/2] + 1) dp[i] = dp[i/2] + 1;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	
	solve();
	
	cout << dp[N];
}

 

2) bottom-up 다른 풀이

#include <bits/stdc++.h>
using namespace std;

int N, dp[1000001];

void solve(){
	dp[1] = 0;
	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);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	
	fill(dp, dp+1000001, 1000001);
	solve();
	
	cout << dp[N];
}

 

3) top-down 풀이

#include <bits/stdc++.h>
using namespace std;

int N, cache[1000001];

int solve(int r){
	// 1. base condition
	if(r == 1) return 0;
	
	// 2. reference
	int &ret = cache[r];
	if(ret != -1) return ret;
	
	ret = solve(r-1) + 1;
	if(r % 3 == 0) ret = min(ret, solve(r/3) + 1);
	if(r % 2 == 0) ret = min(ret, solve(r/2) + 1);
	return ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	
	memset(cache, -1, sizeof(cache));
	cout << solve(N);
}

 

N이 최대 10^6까지 가능하다보니 bottom-up 방식과 top-down 방식의 메모리, 시간 차이가 상당합니다.

BOJ는 스택 메모리가 여유있어 상관없지만, 가급적 stack overflow로부터 안전한 bottom-up으로 구현하는 것을 추천드립니다.

 

2번의 bottom-up 다른 풀이의 경우 https://m.blog.naver.com/kks227/220777103650?referrerCode=1 에서 구현하신 방식인데, 저와는 다른 방식이라 dp 배열을 채워나가는 방식에 대해서 다르게 생각해볼 수 있었습니다. 

 

시간복잡도는 O(N)입니다.