백준 2293 : 동전 1

접근방법

---

동전을 전부 배열에 넣어놓고 하나씩 꺼내면서 전체 배열을 갱신한다.

배열을 갱신할 때 해당 동전의 크기만큼의 앞의 원소를 해당 원소에 더한다.

예를 들어, 동전의 크기가 2일 때 a[i]=a[i]+a[i-2]

왜냐하면 동전의 크기가 2이면 i=2일 때는 동전 하나로 나타낼 수 있지만 i=4일 때는 동전 두 개로 나타내야 하기 때문이다.

 

코드

---

#include <iostream>
using namespace std;

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

	int n, k;
	int coin[101], arr[10001] = { 0, };

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

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

	cout << arr[k];
}