백준 2294번 _ 동전 2

2020-05-09 · 배운 것 · 2분 읽기

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

2294번: 동전 2

풀이방법

메모제이션 문제, 거의 동일한 방식으로 푼 밑의 풀이를 참고.
https://blog.fxjodo.com/blog/100/

백준 2293번 _ 동전 1

전체코드 ( 반복문 풀이 )

#include <iostream>
#include <algorithm>
#include <vector>

#define INF 987654321

using namespace std;
int dp[10001];
vector<int>coins;
int n, k;

void dpInit()
{
	for (int i = 1; i <= k; i++)
		dp[i] = INF;
}

void Input()
{
	cin >> n >> k;
	coins.resize(n+1);
	for (int i = 1; i <= n; i++)
		cin >> coins[i];
	sort(begin(coins), end(coins));
}

void solve()
{
	for (int i = 1; i <= n; i++)
	{
		int coin = coins[i];
		for (int j = 1; j <= k; j++)
		{
			if (j % coin == 0)
				dp[j] = min(j / coin, dp[j]);
			
			if (dp[j] == INF)
				continue;
				
			if (j + coin <= k)
				dp[j + coin] = min(dp[j + coin], dp[j] + 1);
		}
	}
}

int main()
{
	Input();
	dpInit();
	solve();
	if (dp[k] == INF)
		cout << -1 << '\n';
	else
		cout << dp[k];
	return 0;
}