백준 2293 동전 1 / C++

문제 : 2293

풀이 point

백준 9084와 유사한 문제

이해가 안간다면 해당 포스트 참고

1로 10을 만들기 위해서는
1 1 1 1 1 1 1 1 1 1

2로 10을 만들기 위해서는 1로 10을 만들기 위한 방법에 어떠한 덧셈을 해준다.
dp[j] += dp[j-2]를 2부터 10까지 해준다. 그러면 10을 만들기 위해 2를 사용하는 경우의 수 계산이 가능하다.

똑같이 동전 5에 대해서도 dp[j] += d[j-5]를 해주면 10들 만들기 위해 5를 사용하는 경우의 수 계산이 가능하다.

그렇게 계속 누적이 되어 dp[k]에는 총 경우의 수가 적립되게 된다.

코드

//백준 2293, 동전 1
#include <iostream>

int arr[100];
int dp[10'001];

int main(){

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int N, K;

    std::cin >> N >> K;

    for(int i{0}; i<N; ++i){
        std::cin >> arr[i];
    }

    dp[0] = 1;
    for(int i{0}; i<N; ++i){
        for(int j{arr[i]}; j<=K; ++j){
            dp[j] += dp[j - arr[i]];
        }
    }

    std::cout << dp[K];

    return 0;
}