11052번 카드 구매하기

문제 링크

카드 구매하기

문제 풀이

동전2와 제곱수의 합 비슷한 문제이다. 현재 카드 팩을 사지 않는 경우와 남은 개수가 현재의 카드 팩의 개수보다 많거나 같아서 이 카드 묶음을 사는 경우를 재귀 호출로 풀어준다.

구현

#include <iostream> 
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 0;
const int SIZE = 1000;

int N, card[SIZE + 1];

int cache[SIZE + 1][SIZE + 1];

int solve(int remain, int cardNum) {
    if (remain == 0) return 0;
    if (cardNum == 0) return INF;

    int& ret = cache[remain][cardNum];
    if (ret != -1) return ret;

    ret = solve(remain, cardNum - 1);
    if (remain >= cardNum)
        ret = max(ret, solve(remain - cardNum, cardNum) + card[cardNum]);
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    for (int i = 1; i <= N; ++i)
        cin >> card[i];
    memset(cache, -1, sizeof(cache));

    cout << solve(N, N);
    return 0;
}