(c++)백준 2293번: 동전 1

www.acmicpc.net/problem/2293

2293번: 동전 1

[풀이]

DP로 풀 수 있는 문제였다.

DP[x] : 가치의 합이 x가 되는 경우의 수

점화식

if coin[i]<=j : DP[j] += DP[j-coin[i]]

 

#include <iostream>
#include <cstring>//memset
using namespace std;

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

int solution() {
	DP[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			//이번 차례에 i번째 동전을 쓸 수 있는 경우의 수 더하기
			if (coin[i] <= j)
				DP[j] += DP[j - coin[i]];
		}
	}
	return DP[k];
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> coin[i];
	}
	cout << solution() << '\n';
	return 0;
}