처음에는 dp로 접근해서 각 케이스를 열심히 저장 해 주다가, 완성이 불가능한 케이스가 없다는 점을 기억해냈다.
거꾸로 접근해서 큰 수부터 체크 해 가며 기준 수보다 큰 동전을 제외하고 계산 해 주었다. 입력은 앞에서부터, 사용은 뒤에서부터 하므로 stack을 사용하여 풀이하였다.
//
// Created by 전시은 on 2023/02/16.
//
// 문제 :: 동전 0
// 링크 :: https://www.acmicpc.net/problem/11047
// 입력 :: 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
// 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
// 출력 :: 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
#include <stack>
#include <iostream>
using namespace std;
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
stack<int> stackCoins;
int n, nCount = 0;
long long k;
cin >> n >> k;
for(int i = 0; i < n; i++)
{
int nInput;
cin >> nInput;
// 더 큰 동전은 필요하지 않다.
if(nInput <= k)
{
stackCoins.push(nInput);
}
}
while (1)
{
// 결과값 : 카운트
if (k == 0)
{
cout << nCount;
break;
}
if(k < stackCoins.top())
{
stackCoins.pop();
}
else
{
nCount += k / stackCoins.top();
k %= stackCoins.top();
}
}
return 0;
}