Baekjoon2293-동전 1

백준 사이트 2293 - 동전 1 문제입니다.

1. 문제

https://www.acmicpc.net/problem/2293

---

2. Input , Output

---

3. 분류 및 난이도

DB문제입니다.
저같은 경우 코드로 짜기 생각보다 어려워했습니다.
백준에서는 Sliver1의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 배수이거나 새로운 조합인 경우에 경우의 수가 증가하는 것을 알았지만 코드로 짜기가 힘들었습니다.

---

5. code

#include<iostream>
#include<algorithm>
using namespace std;

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

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

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

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

	Input();
	Solve();
	return 0;
}

---

6. 후기

생각보다 어려웠다.