백준 2293 동전 1

문제

2293 동전 1 문제 링크

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

풀이

문제에서 주어진 예제 입력을 사용하면,

3 10
1
2
5

아래 그림처럼 진행된다.(8~10 생략)

동전 1일때(하늘색 형광펜),
dp[1]에서 dp[10]까지 돌면서 dp[i] += dp[i-1]를 계산한다.

동전 2는(분홍색 형광펜),
dp[2]에서 dp[10]까지 돌면서 dp[i] += dp[i-2]를 계산한다.
즉 빨간색 펜으로 표시한 부분을 예로 들면, dp[6]에는 합이 4인 모든 경우에 '동전2'를 하나씩 추가한 경우를 더해줄 수 있기 때문에 dp[6]에는 dp[4]의 값을 더해준다.

소스코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;
    vector<int> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }
    vector<int> dp(k + 1, 0);
    dp[0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = vec[i]; j <= k; j++) {
            dp[j] += dp[j - vec[i]];
        }
    }
    cout << dp[k];

    return 0;
}

DP는 여전히 어렵다 😂 처음에 구성이 같으면 순서가 달라도 같은 경우로 본다는 조건을 생각을 안하고 푸느라 조금 헤맸다.