백준 16568 엔비스카의 영혼

 

16568번: 엔비스카의 영혼

• 두 풀이 방법의 메모리 시간차가 엄청나다...

// Tabulation - Bottom Up
#include <iostream>
#include <algorithm>
using namespace std;
int N, a, b;
int dp[1000001];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> a >> b;
	for (int i = 1; i <= N; ++i) {
		dp[i] = dp[i - 1] + 1;
		if (i - a - 1 >= 0) {
			dp[i] = min(dp[i], dp[i - a - 1] + 1);
		}
		if (i - b - 1 >= 0) {
			dp[i] = min(dp[i], dp[i - b - 1] + 1);
		}
	}
	cout << dp[N];
	return 0;
}

// Memoization - Top Down
#include <iostream>
#include <algorithm>
using namespace std;
int N, a, b;
int dp[1000001];
int solve(int i) {	// i번째 위치까지 소요되는 시간
	if (i == 0) {
		return 0;
	}
	else if (dp[i]) {
		return dp[i];
	}
	else {
		dp[i] = solve(i - 1) + 1;
		if (i - a - 1 >= 0) {
			dp[i] = min(dp[i], solve(i - a - 1) + 1);
		}
		if (i - b - 1 >= 0) {
			dp[i] = min(dp[i], solve(i - b - 1) + 1);
		}
		return dp[i];
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> a >> b;
	solve(N);
	cout << dp[N];
	return 0;
}