최소 동전 개수

면접 대비

시간 제한1초메모리 제한128 MB

요약

n가지 동전 종류가 있을 때 동전을 무제한 사용해 합이 정확히 k가 되도록 만드는 최소 동전 개수를 구하고, 불가능하면 -1을 출력합니다.

문제

n가지 종류의 동전이 주어진다. 각 동전은 필요한 만큼 여러 번 사용할 수 있다.

이 동전들을 사용해 가치의 합이 정확히 k원이 되도록 만들 때, 사용하는 동전 개수의 최솟값을 구하라.

첫째 줄에 n과 k가 주어진다. (1 <= n <= 100, 1 <= k <= 10,000)

다음 n개의 줄에는 동전의 가치가 하나씩 주어진다. 각 가치는 1 이상 100,000 이하이며, 같은 가치의 동전이 여러 번 주어질 수 있다.

합을 k원으로 만들 때 필요한 동전 개수의 최솟값을 출력한다. 만들 수 없다면 -1을 출력한다.