[S1] 16194. 카드 구매하기 2

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

16194번: 카드 구매하기 2

문제 접근 자체를 잘못하여 작성하는 글이다. 나는 처음에 그리디로 해결하려 했다. 하지만, 이유를 모르겠는데 수학적으로 접근하면 문제가 해결되지 않는다. 어쩌다 질문글을 봐버렸다. 동적으로 해결하는 문제였다. 동적이라는 말을 보는 순간 푸는 방법을 알아버렸다.

 

구매하려는 카드의 개수를 위해 지불해야 하는 금액의 최솟값을 동적으로 저장해야 한다. 이것을 최소값이 되면 업데이트 해줘야 한다. 하지만, 이 문제는 하나의 카드를 여러번 구매할 수 있다. 이 때문에 O(N^2)으로 0 ~ 1000까지 카드의 개수에 맞추어 금액이 저장되어야 한다.

 

코드는 다음과 같다.

#include <cstdio>

int main(void) {
    int N, dp[1001]{0}, num; scanf("%d", &N);
    for (int i = 1; i <= N; i++) dp[i] = 1e9;
    for (int i = 1; i <= N; i++) {
        scanf("%d", &num);
        for (int j = 0; j + i <= N; j++) {
            if (dp[j + i] > dp[j] + num) dp[j + i] = dp[j] + num;
        }
    }
    printf("%d", dp[N]);
}

for (int i = 1; i <= N; i++) {
    scanf("%d", &num);
    for (int j = 0; j + i <= N; j++) {
        if (dp[j + i] > dp[j] + num) dp[j + i] = dp[j] + num;
    }
}

 

여기를 살펴보자. 

구매할 카드의 개수가 i, 그 카드의 가격은 num이 된다. 이 카드를 구매할 수 있는 모든 값을 확인하여 최소값이 되도록 업데이트 해주는 것이다. 가장 최소값은 마지막에 dp[N]이 될 것이다.