Baekjoon 11052번 카드 구매하기

문제

https://www.acmicpc.net/problem/11052

걸린 시간

02 : 12 : 18 실패

풀이

C++

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

int n;
int pack[1001], cache[1001];

int dp(int piece){
    // 기저 사례
    if(piece == n)
        return 0;
    // 메모이제이션
    int& ret = cache[piece];
    if(ret != -1)
        return ret;
    // 재귀 함수
    for(int i = 1; i <= n; i++)
        if(piece+i <= n)
            ret = max(ret, dp(piece+i)+pack[i]);
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    memset(pack, 0, sizeof(pack));
    memset(cache, -1, sizeof(cache));
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> pack[i];
    cout << dp(0) << "\n";
    return 0;
}

잦은 코딩실수로 기초 dp 문제를 2시간 씩이나 삽질한 문제이다.

1. 각 단계에서 반환된 값에 현재가 아닌 이전 카드팩의 금액을 더하도록 코딩했다.
2. 변수를 하나 더 두어 금액을 계속 누적해나가는 방법을 사용했다.

1번은 설명하기도 부끄러운 실수이다. 2번은 dfs 처럼 기저 사례에서 목적이 달성되는 문제에 어울리는 방법이다. 또 누적된 금액을 메모이제이션에 이용하는 것은 경우에 따라 완전 탐색과 차이가 없을 수 있다.