한 문구점은 상품권으로만 결제를 받고, 거스름돈을 주지 않습니다. 그래서 손님은 가지고 있는 상품권을 골라 결제 금액을 정확히 맞춰야 합니다.
values[i]: i번째 상품권의 액면가 (서로 다른 값)counts[i]: 손님이 가진 i번째 상품권의 장수 — 이 장수를 넘겨 쓸 수 없습니다target: 결제해야 할 금액액면가별로 몇 장씩 냈는지의 구성이 다르면 서로 다른 결제 방법으로 셉니다. 낸 순서는 구분하지 않습니다.
결제 금액을 정확히 맞추는 방법의 가짓수를 반환하는
solution(values, counts, target) 함수를 작성하세요.
values=[3, 5], counts=[2, 1], target=11 → 1
3원권 2장 + 5원권 1장 = 11. 이 한 가지뿐입니다.
(5원권을 쓰지 않으면 3의 배수로 11을 만들 수 없습니다.)
values=[1, 2, 5], counts=[5, 3, 2], target=8 → 4
(1원권, 2원권, 5원권) 장수로 적으면
(2, 3, 0) → 2 + 6 = 8
(4, 2, 0) → 4 + 4 = 8
(1, 1, 1) → 1 + 2 + 5 = 8
(3, 0, 1) → 3 + 5 = 8
values=[3], counts=[2], target=9 → 0
3원권을 3장 낼 수 있다면 가능하지만, 2장밖에 없으므로 방법이 없습니다.target이 0이면 한 장도 내지 않는 방법 1가지가 있습니다시간 복잡도 목표: O(values.length × target × max(counts))
▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.