백준(BOJ) 2294번 동전 2

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

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

나의 풀이:

반복적 동적 계획법을 통해 해결해보자 . cache[i] 는 i 원을 만들 수 있는 최소 동전의 수로 놓고 동적 계획법을 짜보자

예제 )

코드 ( C++ )

#include <iostream>

#include <algorithm>

using namespace std;

int n, k;

int coin[101];

int cache[10001];

const int INF = 987654321;

int solve()

{

// INF 로 1~k까지  cache 초기화

for (int i = 1; i <= k; ++i)

cache[i] = INF;

for (int i = 1; i <= n; ++i)

for (int j = coin[i]; j <= k; ++j)

cache[j] = min(cache[j], cache[j - coin[i]] + 1);

// k원을 만들수 없는 경우 즉 한번도 갱신이 안되었으면 -1 출력

if (cache[k] == INF)

return -1;

else

return cache[k];

}

int main()

{

cin >> n >> k;

for (int i = 1; i <= n; ++i)

cin >> coin[i];

// 0원을 만들수있는 수는 0이므로 cache[0] = 0

cache[0] = 0;

int ans = solve();

cout << ans << "\n";

return 0;

}