문제 설명
x 원과 y 원에 해당하는 두 종류의 동전이 충분히 존재합니다. 이 동전들을 이용해 금액 change 원을 거슬러 줄 때 필요한 최소 동전 개수를 구하려고 합니다.
동전의 단위 x, y와 거스름돈 change가 주어졌을 때, 정확히 change만큼 거슬러 주기 위해 필요한 최소 동전 개수를 반환하는 solution 함수를 작성하시오.
만약 어떤 조합으로도 정확히 change를 거슬러 줄 수 없다면 -1을 반환합니다.
제한 사항
x와y는 1 이상 10,000 이하의 자연수입니다.x와y는 서로 다른 자연수입니다.change는 1 이상 1,000,000,000 이하의 자연수입니다.
예시 테스트케이스 설명
| 테스트케이스 번호 | x | y | change | return |
|---|---|---|---|---|
| 1 | 3 | 5 | 11 | 3 |
| 2 | 2 | 6 | 5 | -1 |
| 3 | 4 | 7 | 36 | 6 |
1번 테스트케이스 설명
- 정확히 11원을 만들 수 있는 경우의 조합은 아래의 경우가 유일합니다.
- 5원짜리 동전 1개 + 3원짜리 동전 2개: 5 + 3 x 2 = 11 (총 3개)
2번 테스트케이스 설명
- 2와 6의 조합에서 어떠한 조합으로도 5원을 거슬러 줄 수 없습니다.
3번 테스트케이스 설명
- 정확히 36원을 만들 수 있는 경우의 조합은 아래와 같으며 최소 동전 사용 개수는 6개입니다.
- 4원짜리 동전 9개: 4 x 9 = 36 (총 9개)
- 4원짜리 동전 2개 + 7원짜리 동전 4개: 4 x 2 + 7 x 4 = 36 (총 6개)