'알고리즘' 카테고리의 다른 글
| [EASY] 백준 2167 2차원 배열의 합 (0) | 2018.04.02 |
|---|---|
| [DP] 백준 14916 거스름돈 (0) | 2018.04.02 |
| [DP] 백준 동전 2 2294 (0) | 2018.04.02 |
| [DP] 백준 2011 암호코드 (0) | 2018.01.02 |
| [그래프] 백준 1987 알파벳 (0) | 2017.12.14 |
[DP] 백준 9084 동전
2018. 4. 2. 12:47
if (sum == 0) {
return 1;
}
if (sum < 0) {
return 0;
}
if (cache[sum][index] != -1) {
return cache[sum][index];
}
여기서 cache를 if 앞에 놔두면 런타임 에러가 났다.
이 코드가 왜 성공하는지 100% 는 이해 못했지만 계속 하다보면 될 것 같다. 한발짝 나간 것 같다.
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n;
int money;
int arr[21];
int cnt;
int cache[10011][100];
int go(int sum,int index) {
if (sum == 0) {
return 1;
}
if (sum < 0) {
return 0;
}
if (cache[sum][index] != -1) {
return cache[sum][index];
}
cache[sum][index]++;
int& ret = cache[sum][index];
for (int i = index; i < n; ++i) {
ret += go(sum - arr[i],i);
}
return ret;
}
int main(void)
{
int t;
cin >> t;
while (t--) {
memset(arr, 0, sizeof(arr));
memset(cache, -1, sizeof(cache));
cnt = 0;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
cin >> money;
cout << go(money,0) << endl;
}
return 0;
}