문제

문제 분석

DFS Bruteforce로 전부 처리하는 경우 시간복잡도가 상당할 것이다.

이때, bruteforce중에 반복적으로 조사하는 부분이 생기는 걸 확인할 수 있다.
12원->10원->8원->(다음)
12원->11원->8원->(다음)

결국 DP-tabulation으로 풀 수 있다.
dp로 푼다면 축의 조합을 어떻게 설정할까?

가격을 축으로 하는 1D DP면 충분하다.

알고리즘

• DP-tabulation

자료구조

• 1D vector

결과

#include <iostream>
#include <vector>

using namespace std;

struct Ad{
    int cost;
    int numOfGet;
};

const int MAX_INT = ~(1<<31);

int C, N;

int main( void )
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    cin >> C >> N;

    vector<Ad> ads(N);
    {
        int cost, numOfGet;
        for ( int i = 0; i < N; i++ ){
            cin >> cost >> numOfGet;
            ads[i] = Ad{cost, numOfGet};
        }
    }

    vector<int> table(C+1,MAX_INT);
    table[0] = 0;
    for ( int c = 1; c <=C; c++ ){
        int minCost = MAX_INT;
        for ( int adsIdx = 0; adsIdx < N; adsIdx++){
            int newCost = MAX_INT;

            Ad ad = ads[adsIdx];
            int remain = c - ad.numOfGet;
            if ( remain < 0 )
                newCost = ad.cost;
            else {
                newCost = table[remain] + ad.cost;
            }

            if ( minCost > newCost )
                minCost = newCost;
        }
        table[c] = minCost;
    }

    cout << table[C];
}

Other

dp는 2d 많긴 하지만, 1개 또는 3개 또는 그 이상일 수도 있다.
축이 덜 필요한지, 더 필요하진 않은 지 한번 더 살펴보는 습관을 가지자.