본문 바로가기

알고리즘

최소 동전 개수 찾기

Basic 100 · 51번Lv. 3동적 계획법

최소 동전 개수 찾기

문제 설명

다양한 가치의 동전들이 주어질 때, 특정 금액을 만드는 데 필요한 최소한의 동전 개수를 찾는 함수를 작성해주세요. 각 동전은 무한정 사용할 수 있다고 가정합니다.

예를 들어, 동전의 가치가 [1, 5, 10]이고, 만들어야 할 금액이 18이라면, 최소 동전 개수는 5개입니다 (10, 5, 1, 1, 1).


제한 사항

  • 동전의 종류 수는 1 이상 10 이하입니다.
  • 각 동전의 가치는 1 이상 100 이하의 정수입니다.
  • 만들어야 하는 금액은 1 이상 10,000 이하의 정수입니다.
  • 주어진 동전으로 만들 수 없는 금액은 주어지지 않습니다.
  • 입력 data는 {"coins": 동전 가치 리스트, "amount": 금액} 형태로 주어집니다.

입출력 예

입력 (동전 가치, 금액)반환값 (최소 동전 개수)
[1, 5, 10], 185
[1, 3, 4], 62
[1], 100100

입출력 설명

주어진 동전들을 사용하여 특정 금액을 만드는 데 필요한 최소한의 동전 개수를 계산합니다. 18을 만들려면 10, 5, 1, 1, 1로 동전 5개가 필요합니다.

두 번째 예시에서 큰 동전부터 고르면 4, 1, 1로 3개가 되지만, 3, 3을 쓰면 2개로 만들 수 있으므로 2를 반환합니다.

예시 테스트

#입력기대값
1{"coins": [1, 5, 10], "amount": 18}5
2{"coins": [1, 3, 4], "amount": 6}2
3{"coins": [1], "amount": 100}100

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 14개도 함께 채점해요.