글 읽기 - 코딩을 하다가 런타임 에러에 대해서 질문드립니다.

rlarlghks970113 4년 전 0

일단 짠 방식은 탑다운과 메모이제이션을 이용해서 dp를 짯는데요

제가 코딩을 하다가 이해 안되는 부분을 발견했어요

27번째 줄에 for문을 주석 처리한 for문으로 돌리면 런타임 에러가 뜨더라고요

어차피 n < 1일때 0값을 리턴해줘서 cache배열에서 스택오버플로우가 뜰리가 없다고 생각하는데요

신기한건 원래 코드에 써있는 방식대로 하면은 제 컴파일러에서는 런타임 에러가 안뜬다는 겁니다.

고수분들 이유가 뭔지 자세하게 부탁드릴수 있을까요?

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

//메모이제이션
vector<int> cache(100001, -1);

int min(int a, int b)
{
	return a > b ? b : a;
}
//탑다운
//점화식 d[n번째] =  max(d[n-i^2]) : i는 1~sqrtn까지) + 1;
//매개인자 n
int dp(int n)
{
	//기저사례
	if (n < 1) return 0;
	//메모이제이션
	int ret = cache[n];
	if (ret != -1) return cache[n];


	int sqrtn = static_cast<int>(sqrt(n));
	int minimum = 100000;
	for (int i = sqrtn; i >= 1; --i)//이 부분을 for(int i = 1; i<=sqrtn;++i)로 바꾸면 스택오버플로우가 뜹니다..
	{

		minimum = min(minimum, dp(n - i * i));
	}


	return cache[n] = minimum + 1;
}

int main()
{
	ios::sync_with_stdio(0);
	cout.tie(0);
	cache[0] = 0;
	cache[1] = 1;
	int n;
	cin >> n;
	cout << dp(n) << '\n';

	return 0;
}