런타임에러

다이나믹 프로그래밍문제를 풀다보니

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int a[100001];
int coaunt = 0;
int dp(int num) {
	if (num == 1) return 0;
	if (a[num] != 0) return a[num];
	//cout << coaunt++ << " : " <<num<<"\n";

	if (num % 3 == 0 && num % 2 == 0)
		return a[num] = min(min(dp(num / 3) + 1, dp(num / 2) + 1), dp(num - 1) + 1);
	else if (num % 3 == 0)
		return a[num] = min(dp(num / 3) + 1, dp(num - 1) + 1);
	else if (num % 2 == 0)
		return a[num] = min(dp(num / 2) + 1, dp(num - 1) + 1);
	else
		return a[num] = dp(num - 1) + 1;
}
int main(void) {
	int num;
	cin >> num;
	cout << dp(num);

	//system("pause");
}

함수가 3380개 정도 겹치니 stack overflow로 런타임 에러가 뜨는것 같다.

 

top-down이 아니라 botton-up으로 하니 해결되었다.

 

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

int a[1000001];

int main() {
	int n;
	cin >> n;
	a[1] = 0;
	for (int i = 2; i <= n; i++) {
		a[i] = a[i - 1] + 1;
		if (i % 2 == 0 && a[i] > a[i / 2] + 1) 
			a[i] = a[i / 2] + 1;
		if (i % 3 == 0 && a[i] > a[i / 3] + 1) 
			a[i] = a[i / 3] + 1;
	}
	cout << a[n] << '\n';
	//system("pause");
	return 0;
}

 

보통 top-down방식으로 다이나믹을 풀때는 재귀함수를 사용하고 botton-up방식으로 풀때는 포문을 사용하는데 botton-up 방식이 조금더 빠르고 좋은것 같다. 

하지만 top-down방식이 눈에 더잘들어오고 쉽다. 

문제마다 적절한 방식을 사용해야 겠다..