백준 2293번 동전 1 문제풀이(C++)

백준 2293번 동전 1

아이디어

각각의 동전으로 만들 수 있는 경우의 수

	1	2	3	4	5	6	7	8	9	10
1원	1개	1개	1개	1개	1개	1개	1개	1개	1개	1개
2원		1개		1개		1개		1개		1개
5원					1개					1개

위 표를 바탕으로 점화식 작성

dp[j] = dp[j]+ dp[j - coin[i]];

점화식을 바탕으로 재구성

	1	2	3	4	5	6	7	8	9	10
1원일 때 dp[i]	1	1	1	1	1	1	1	1	1	1
2원일 때 dp[i]	1	2	2	3	3	4	4	5	5	6
5원일 때 dp[i]	1	2	2	3	4	5	6	7	8	10

문제풀이

#include<bits/stdc++.h>
using namespace std;
int coin[101], dp[100001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> coin[i];
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = coin[i]; j <= k; j++)
			dp[j] = dp[j]+ dp[j - coin[i]];
	}
	cout << dp[k] << '\n';
	return 0;
}