[백준 2293] 동전 1

문제 링크 => 2293번: 동전 1 (acmicpc.net)

2293번: 동전 1

---

다이나믹 프로그래밍 문제이다.

 

오름차순으로 정렬된 동전을 통해 k원을 만족하게 되도록 하는 동전들의 개수를 구하는 문제이다.

 

예를들어서 동전 1원 하나만 들어왔다고 가정하자.

	1	2	3	4	5	6	7	8	9	10(k)
1	1	1	1	1	1	1	1	1	1	1

이때 1원 이후로 값이 전부 채워진것을 확인할 수 있다.

dp[1] = dp[1] + dp[0] (이때 dp[0] = 1 이라고 설정) = 0 + 1 =1

...

dp[4] = dp[4] + dp[3] = 0 + 1 = 1

...

dp[10] = dp[10] + dp[9] = 0 + 1 = 1

 

그 후에 2원이 들어왔다고 가정하자.

	1	2	3	4	5	6	7	8	9	10(k)
1	1	2	2	3	3	4	4	5	5	6

이때 2원 이후로 값이 증가된것을 확인할 수 있다. 

dp[2] = dp[2] + dp[0] (이때 dp[0] = 1 이라고 설정) = 1 + 1 = 2

...

dp[5] = dp[5] + dp[3] = 1 + 2 = 3

...

dp[10] = dp[10] + dp[8] = 1 + 5 = 6

 

마지막으로 5원이 들어왔다고 가정하자.

	1	2	3	4	5	6	7	8	9	10(k)
1	1	2	2	3	4	5	6	7	8	10

이때 5원 이후로 값이 증가된 것을 확인할 수 있다.

dp[5] = dp[5] + dp[0] (이때 dp[0] = 1 이라고 설정) = 3 + 1 = 4

...

dp[8] = dp[8] + dp[3] = 5 + 2 = 7

...

dp[10] = dp[10] + dp[5] = 6 + 4 =10

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

long long dp[10001];
int arr[101];
int n, k;

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

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

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

	return 0;
}