백준 2293번

DP는 DP인데 문제를 이해하는데 좀 오래걸렸습니다. 간단하게는 모든 코인에 대해 메모제이션을 하면 되지만 메모리제한이 엄격해 다른 방법을 찾아야 합니다.

두번 중첩된 for문을 설명해보자면

1. i가 0부터 n까지 반복문을 실행합니다. 바깥쪽 반복문은 i번째 코인이 사용되는 경우의 수를 구하겠다는 것을 의미합니다.

2. 안쪽에 있는 중첩된 반복문은 i번째 coin의 값부터 시작합니다. 첫번째 반복문을 통해선 무조건 1이 더해집니다(코인값 j와 같은 가치의 코인을 사용하는 경우). 이후 코인값 j에서 i번째 코인의 값을 뺐을때의 값을 구할 수 있는 경우의 수를 더해줍니다. 이 반복문을 통해 coins[i]가 j값을 만들기 위해 사용된 모든 경우의 수를 구할 수 있습니다.

#include <cstdio>
 
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
 
    int* coins = new int[n+1];
    int* coinSum = new int[k+1]();
    for (int i = 0; i < n; i++) {
        scanf("%d", &coins[i]);
    }
 
    coinSum[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = coins[i]; j <= k; j++) {
            coinSum[j] += coinSum[j - coins[i]];
        }
    }
 
    printf("%d\n", coinSum[k]);
}