[BOJ] 2293번 동전 1 c++

https://www.acmicpc.net/problem/2293

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

---

입력 1
3 10
1
2
5

출력 1
10

---

#include <cstdio>
using namespace std;

int main() {
  int n, k;
  int coin[101] = {0,};
  int dp[10001] = {0,};
  scanf("%d %d", &n, &k);
  for(int i = 1; i <= n; i++)
    scanf("%d", &coin[i]);

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

  printf("%d\n", dp[k]);
}

(* 이 문제는 메모리 4MB로 제한되어 있어서 점화식 외에도 조금 고민할 필요가 있다.)
동전 여러 개가 입력으로 주어지고 다음을 수행한다.
1. 첫번째 동전으로 임의의 값 m(0 < m <= k)을 만들 수 있는 경우의 수를 구한다.
2. 두번째 동전을 더해서 임의의 값 m(0 < m <= k)을 만들 수 있는 경우의 수를 구한다.
3. n번째 동전까지 차례대로 더해서 임의의 값 m(0 < m <= k)을 만들 수 있는 경우의 수를 구한다.

n번째 동전까지 사용할 때 m을 만드는 경우
= n - 1번째 동전까지 사용할 때 m을 만드는 경우
+ n번째 동전까지 사용할 때 m - n번째 동전의 크기를 만드는 경우 (n번째 동전을 추가함으로써 그만큼 값이 대체될 것이기 때문)

예시) 동전: [2, 5], k = 7

-	0	1	2	3	4	5	6	7
어떠한 동전도 사용 x	1	0	0	0	0	0	0	0
첫번째 동전을 추가했을 때	1	0	1	0	1	0	1	0
두번째 동전을 추가했을 때	1	0	1	0	1	1	1	1