글 읽기 - 쉬운 DP 하나만 도와주세요!!ㅜ (주석 있음!!)

devbelly 4년 전 0

안뇽하세요. 메모리 초과가 떴는데 어떻게 해결해야할지 몰라 질문드립니다.

순서를 강제하는 방법으로 이전에 사용한 값을 dp인자로 받았는데 메모리를 줄이려면 어떡해야하나요?

#include <bits/stdc++.h>
using namespace std;

int coin[21];
int num, goal;
int cache[10001][10001];

int solve(int m, int n) {

	if (m == 0) return 1; // BASE CASE #1 : 동전을 알맞게 써서 현재 금액 M==0 , 즉 갯수 1개 추가
	if (m < 0) return 0; // BASE CASE #2 : 동전을 알맞게 못씀 , 잘못 썼으므로 갯수는 0개

	int& ret = cache[m][n + 1]; // 처음에 -1이 인자로 오므로 N+1 사용
	if (ret != -1) return ret;
	ret = 0;

	for (int i = 1;i <= num;++i) { // 순서를 강제하기 위한 행동. 동전을 뽑는 조합이므로 뽑는 순서는 중요하지 않다.
		if (n <= coin[i]) // 만약에 이전에 사용한 값이(n) coin[i]보다 작다면
			ret += solve(m - coin[i], coin[i]); // coin[i]를 다음동전으로 사용 ,
	}


	return ret;
}

int main() {
	int T; // 테스트 케이스
	cin >> T; // 를 입력받자
	while (T--) {
		memset(cache, -1, sizeof(cache)); 
		cin >> num; // 동전의 갯수 입력받자
		for (int i = 1;i <= num;++i) // 동전들의 정보 입력받기( 몇원짜리 동전인지)
			cin >> coin[i];
		cin >> goal; // 목표치
		cout << solve(goal, -1) << '\n'; // 목표치와 이전에 사용한 동전의 값. 처음엔 아무 동전도 안썻으니 -1
	}

	return 0;
}