백준 2293 동전 1 (C++)

2293번: 동전 1

생각이 필요한 dp 문제이다. 주어진 동전을 이용해 k원이 될 경우의 수를 구하는 문제인데 처음에는 DFS를 사용했다가 시간 초과가 났었다. dp 배열 구조에 대해 말해보자면 아래와 같다.

• dp[j] = i -> j원의 경우의 수 = i개
• dp[j] = dp[j] + dp[j-A[i]] j원의 경우의 수 = 기존 j원의 경우의수 + 동전을 더하기 전의 경우의 수

반복문을 통해 위의 조건을 맞추어 dp배열을 채워나가 k원의 경우의 수를 구하게 된다.
dp 문제를 좀 더 연습해야겠다. 아직 어렵다.

#include <iostream>

using namespace std;

int n, k;
int A[101];
int dp[10001];

void solution() {
    dp[0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = A[i]; j <= k; j++) {
            dp[j] += dp[j - A[i]];
        }
    }

    cout << dp[k];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }

    solution();

    return 0;
}