Baekjoon2294-동전 2

백준 사이트 2294 - 동전 2 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

DP문제입니다. 동전 1의 문제에서 모든 경우의 수 -> 최소값으로 바뀐 것입니다. 백준에서는 Sliver1의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 동전 1의 코드를 참고하였습니다.
• memset()함수를 이용해서 0이 아닌 값으로 초기화하는 것은 굉장한 위험이 따릅니다. Byte 계산 때문이라는데 자세한건 ‘memset 주의할 점’으로 검색하면 많이 나옵니다.

---

5. code

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

int dp[10001] = { 0, };
int arr[101] = { 0, };
int n, k;
//확인용 함수
void dpprint()
{
	for (int i = 0; i <= k; ++i)
	{
		cout << dp[i] << " ";
	}
}

void Input()
{
	cin >> n >> k;
	for (int i = 0; i < n; ++i)
		cin >> arr[i];
	//dp초기화
	for (int i = 0; i <= k; ++i)
	{
		dp[i] = 10001;
	}
}

void Solve()
{

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


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

	Input();
	Solve();

	return 0;
}

---

6. 후기

어렵지 않았다. 빠르게 풀려고 노력했다.