동전 1 //2293

• 문제
  n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.
  사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
  
  // 시간 제한: 0.5초, 메모리 제한: 4MB

• 입력
  첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

• 출력
  첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

// Created by dongwan-kim on 2022/08/13.
#include<iostream>

using namespace std;

int dp[10001];
int n, k;

int main() {
    cin >> n >> k;
    int coin[n];	//동전 갯수만큼 배열 선언
    for (int i = 0; i < n; i++) {
        cin >> coin[i];		//동전 가치 삽입
    }
    dp[0] = 1;		
    for (int i = 0; i < n; i++) {
        for (int j = coin[i]; j <= k; j++) {
            dp[j] += dp[j - coin[i]];	//점화식
        }
    }

    cout << dp[k];
}

풀이

dp알고리즘을 이용하여 문제를 해결했다.

로직은 coin[i] 가치의 동전으로 만들 수 있는 경우에 카운팅을 덮어주는 방식?이다.

점화식은 dp[j] += dp[j - coin[i]] 이다.