백준 2293번: 동전 1

문제

문제 바로가기> 백준 2293번: 동전 1

풀이

dp[k] : 가치의 합이 k원이 되는 경우의 수

1. dp[0] : 가치의 합이 0원이 되는 경우의 수 = 1
2. dp[k] : dp[k] = dp[k] + dp[k - coin[i]]
   * dp[k - coin[i]] : coin[i]를 사용 -> coin[i]만큼의 가치를 비운 후 그 경우의 수를 더해준다!

#include<iostream>
#include<cstring>
#define MAX_N 101
#define MAX_K 10001
using namespace std;

int N, K;
int coin[MAX_N];
int dp[MAX_K];

void input() {
	cin >> N >> K;
	for (int i = 1; i <= N; i++) cin >> coin[i];
}

void solution() {
	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];
}

int main() {
	input();
	solution();
}