7-Y 성냥개비 문제 최소값을 Top-Down으로 풀었을 때 질문이 있습니다

안녕하세요, 큰돌님 강의 열심히 듣고 있는 수강생입니다.

제 풀이입니다. 사실상 강의 코드와 거의 일치합니다.

(다른 점은 올 수 있는 숫자 중 필요 성냥개비 수가 같은 수 중 큰 수를 제거하고 0,1,2,4,6,7,8 에 대해서만 따로 배열을 만들어 돌렸다는 정도입니다)

https://www.acmicpc.net/source/79322370

강의 내용을 바탕으로 바텀업 방식과 탑다운 방식으로 모두 풀어보았는데요.

문제 해설에 남겨주신 풀이도 바텀업인 것을 보니 이 문제의 정통 풀이법은 아마 바텀업인 것 같습니다.

탑다운 방식의 풀이가 틀린 것은 아닌데..

테스트 케이스가 여러 개 주어지는 문제이다보니 성냥개비 개수를 작은 순으로 (4개, 7개, 10개..) 주면 맞는데, 처음 주어지는 성냥개비 개수가 큰 경우(예를 들어 100개부터 주어지는 경우) 에는 100개에 대한 top-down을 돌면서 거쳐온 중간 값들을 dp에 저장하는데 이때 '첫째 자리에는 0이 올 수 없다' 라는 조건을 만족하지 못하는 수가 다수 저장됩니다.

입력으로 주어진 수 x에 대해서는

if (left == x && num == 0) continue;

해당 구문으로 첫째 자리에 0이 오는 것을 방어하는데, 이후 입력으로 받은 수가 dp 테이블에 기록되어있다면 바로 return해버려서 되다 만 중간값을 그냥 반환해버리는 문제가 있는 것 같습니다.

그렇다고 모든 입력에 대해 dp테이블을 전부 비웠다가 다시 탑다운으로 일일이 계산하는 것은 너무나 비효율적같아 보이는데.. 이렇기 때문에 이 문제 풀이는 바텀업이 정배(?)인건가요?

아니면 탑다운 방식에서 제가 뭘 놓치고 있는 것이 있을까요?

string findMin(int here){  
	if(here == 0) return ""; 
	string &ret = dp[here];  
	if(ret != MAX_STR) return ret;  
	for(int i = 0; i <= 9; i++){ 
		if(here - a[i] < 0) continue; 
		if(here == n && i == 0) continue; 
		ret = get_min_str(ret, to_string(i) + findMin(here - a[i]));
	} 
	return ret; 
}