DP 여러 문제를 풀어보았는데 이와같은 방법으로 해결한문제는 처음이였다. 매 분기를 dp로 저장하는 방법을 사용하는 것이 아닌 현재 값에 해당하는 dp를 만들어 저장하는 방식이였다. 쉽게 설명하자면

1원, 2원, 3원을 이용해서 7원을 만들기 위해서는 1,2,3원이 필요로 한 곳에만 사용을 하면 됐다.

dp(3) += dp(0)
dp(4) += dp(1)
dp(5) += dp(2)
dp(6) += dp(3)
dp(7) += dp(4)

정답 출처

#include <iostream>
#include <vector>
#define endl "\n"

using namespace std;

int n, k;
int coin[10100];
int dp[10100];
int ct = 0;

void input() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> coin[i];
    }
}

void dynamic() {
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = coin[i]; j <= k; j++) {
            dp[j] += dp[j - coin[i]];
        }
    }
}

int main() {
    input();
    dynamic();
    cout << dp[k] << endl;
    return 0;
}