Coin Change

서로 다른 몇 가지 액면가의 동전이 무제한으로 있고, 가능한 한 적은 동전을 사용해 정확한 금액을 지불하고 싶습니다.

맞는 것 중 가장 큰 동전을 집는 것이 좋은 방법처럼 보이지만, 실패할 수 있습니다. 동전이 [1, 3, 4]이고 금액이 6일 때, 가장 큰 동전을 먼저 사용하면 4 + 1 + 1이 되어 동전 세 개가 필요하지만, 3 + 3은 두 개만 필요합니다.

더 안전한 방법은 작은 금액부터 답을 만들어 가는 것입니다. fewest[t]를 합계가 t가 되는 데 필요한 최소 동전 수라고 합시다. 0을 지불하는 데는 동전이 필요하지 않습니다. 그 외의 t에 대해서는 마지막에 사용한 동전의 액면가를 c라고 할 때, 그 동전을 사용하기 전 남은 금액은 t - c이므로 다음과 같습니다.

fewest[t] = 1 + the smallest fewest[t - c] (단, t보다 크지 않은 모든 동전 c에 대해).

[1, 3, 4]의 경우: fewest[3] = 1이고, fewest[6] = 1 + fewest[3] = 2입니다. 도달 가능한 금액으로 이어지는 동전이 없다면 t는 전혀 지불할 수 없습니다.

coinChange라는 함수를 작성하세요. 이 함수는 서로 다른 동전 값의 목록인 coins와 정수 amount를 받아, 합계가 정확히 amount가 되는 데 필요한 최소 동전 개수를 반환합니다. 각 동전 값은 원하는 만큼 사용할 수 있습니다. 금액을 만들 수 없으면 -1을 반환하고, amount가 0이면 0을 반환하세요.

예를 들어, coins = [2, 5, 10]이고 amount = 27이면 4를 반환합니다(10 + 10 + 5 + 2). coins = [4, 6]이고 amount = 7이면 -1을 반환합니다.

제약 조건: 1 <= coins.length <= 12, 1 <= coins[i] <= 10^4, 모든 값은 서로 다르며, 0 <= amount <= 10^4입니다.