문제

입력

입출력 예시

코드

#include <iostream>
#include <vector>
#define INF ~0U >> 2
using namespace std;

vector<int> cache;
int N, a, b;

int main() {  
	cin >> N >> a >> b;
	cache = vector<int> (N + 1, INF);
	cache[0] = 0;
	for(int i = 1; i <= N; i++){
		if(i - a >= 0) cache[i] = min(cache[i - a] + 1, cache[i]);
		if(i - b >= 0) cache[i] = min(cache[i - b] + 1, cache[i]);
	}
	
	cout << (cache[N] == INF ? -1 : cache[N]);
	return 0;
}

DP에서 재귀 안 쓰고 점화식 구해서 메모이제이션만 이용해서 푸는 연습을 해봐야겠다. 너무 (틀에 박힌 사고를 해서) 쓸데없는 낭비를 하는듯.
쓸데없는 낭비를 하며 오류가 난 코드는 아래에. 그런데 왜 런타임 에러가 발생했는지는 도무지 모르겠다😥

TC 18, 22에서 runtime error

#include <iostream>
#include <vector>
#define INF ~0U >> 2
using namespace std;

vector<int> cache;
int N, a, b;

int ache(int remain, int cnt) {
	if(remain == 0) return cnt;
	int& ret = cache[remain];
	if(ret != INF) return ret;
	if(remain < a) return INF;
	if(remain < b) return ret = ache(remain - a, cnt + 1);
	return ret = min(ache(remain - a, cnt + 1), ache(remain - b, cnt + 1));
}

int main() {
	cin >> N >> a >> b;
	cache = vector<int> (N + 1, INF);
	int ans = ache(N, 0);
	cout << (ans == INF ? -1 : ans);
	return 0;
}

처음 코드 짤 때부터 아.. 이거 아닌데.... 조건이 너무 많은데... 라고 생각하면서 짜긴 했다. 근데 뭐.. 맞긴 맞으니까... 라고 생각했는데 테스트 케이스 2개를 통과하지 못했다🫥

발전기 Q&A에 있던 거랑 마찬가지로 재귀적으로 풀어서 런타임 에러가 발생했을 것 같기도 하고..
왜! 몇 개만 통과를 못 하는건데!!! 걍 이유가 미친듯이 궁금하다.

➕ 어떤 분이 댓글을 달아주셨는데 약 14만 번 이상의 재귀가 이루어지면 스택 메모리 런타임 에러가 나오는 것 같다고 알려주셨다! 역시 재귀가 문제구나~