#033 · DP어려움유한 개수 배낭,DP

환전기 최소 지폐 장수

문제

무인 환전기가 손님이 요청한 금액을 지폐로 지급하려 합니다. 환전기 안에는 여러 종류의 지폐가 들어 있는데, 종류마다 남은 재고가 정해져 있어 무한정 쓸 수 없습니다.

지폐 정보 bills가 주어집니다. bills[i] = [액면가, 재고 수량]이며, i번 지폐는 최대 재고 수량장까지만 사용할 수 있습니다.

요청 금액 amount를 정확히 맞추면서 사용하는 지폐 장수를 최소로 하고 싶습니다. 최소 장수를 반환하고, 재고로는 금액을 정확히 맞출 수 없으면 -1을 반환하는 solution(bills, amount) 함수를 작성하세요.

예시

bills	amount	결과
`[[1000, 3], [5000, 2], [10000, 1]]`	`17000`	`4`
`[[1000, 2], [5000, 1]]`	`8000`	`-1`
`[[500, 4], [2000, 2]]`	`3000`	`3`
`[[1, 10], [6, 2], [9, 1]]`	`12`	`2`

예시 1 설명: 10000 + 5000 + 1000 + 1000으로 4장입니다. 3장 이하로는 17000원을 만들 수 없습니다.

예시 2 설명: 재고를 모두 써도 1000 × 2 + 5000 = 7000원뿐이라 8000원을 만들 수 없습니다.

예시 3 설명: 2000 + 500 + 500으로 3장입니다.

예시 4 설명: 6 + 6으로 2장입니다. 큰 액면가부터 욕심내어 9를 먼저 쓰면 9 + 1 + 1 + 1로 4장이 되어 최선이 아닙니다.

제약 조건

1 ≤ bills.length ≤ 12
1 ≤ 액면가 ≤ 100,000, 액면가는 서로 다릅니다.
1 ≤ 재고 수량 ≤ 100
0 ≤ amount ≤ 20,000
amount가 0이면 답은 0입니다.

시간 복잡도 목표: O(amount × 전체 재고 수량의 합)

공간 복잡도 목표: O(amount)

테스트 케이스

예시 1: 10000+5000+1000+1000 → 4장

입력: bills = [[1000,3],[5000,2],[10000,1]], amount = 17000

출력: 4

예시 2: 재고 총합이 7000원 → 불가능

입력: bills = [[1000,2],[5000,1]], amount = 8000

출력: -1

예시 3: 2000+500+500 → 3장

입력: bills = [[500,4],[2000,2]], amount = 3000

출력: 3

예시 4: 그리디 함정 — 6+6이 최소

입력: bills = [[1,10],[6,2],[9,1]], amount = 12

출력: 2

엣지: 요청 금액 0 → 0장

입력: bills = [[1000,3]], amount = 0

출력: 0

엣지: 재고는 넉넉하지만 홀수 금액을 만들 수 없음

입력: bills = [[4,10],[6,10]], amount = 9

출력: -1

solution.ts

에디터 로딩 중…

▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.

환전기 최소 지폐 장수

문제

지폐 정보 bills가 주어집니다. bills[i] = [액면가, 재고 수량]이며, i번 지폐는 최대 재고 수량장까지만 사용할 수 있습니다.

예시

bills	amount	결과
`[[1000, 3], [5000, 2], [10000, 1]]`	`17000`	`4`
`[[1000, 2], [5000, 1]]`	`8000`	`-1`
`[[500, 4], [2000, 2]]`	`3000`	`3`
`[[1, 10], [6, 2], [9, 1]]`	`12`	`2`

예시 1 설명: 10000 + 5000 + 1000 + 1000으로 4장입니다. 3장 이하로는 17000원을 만들 수 없습니다.

예시 2 설명: 재고를 모두 써도 1000 × 2 + 5000 = 7000원뿐이라 8000원을 만들 수 없습니다.

예시 3 설명: 2000 + 500 + 500으로 3장입니다.

예시 4 설명: 6 + 6으로 2장입니다. 큰 액면가부터 욕심내어 9를 먼저 쓰면 9 + 1 + 1 + 1로 4장이 되어 최선이 아닙니다.

제약 조건

1 ≤ bills.length ≤ 12
1 ≤ 액면가 ≤ 100,000, 액면가는 서로 다릅니다.
1 ≤ 재고 수량 ≤ 100
0 ≤ amount ≤ 20,000
amount가 0이면 답은 0입니다.

시간 복잡도 목표: O(amount × 전체 재고 수량의 합)

공간 복잡도 목표: O(amount)

테스트 케이스

예시 1: 10000+5000+1000+1000 → 4장

입력: bills = [[1000,3],[5000,2],[10000,1]], amount = 17000

출력: 4

예시 2: 재고 총합이 7000원 → 불가능

입력: bills = [[1000,2],[5000,1]], amount = 8000

출력: -1

예시 3: 2000+500+500 → 3장

입력: bills = [[500,4],[2000,2]], amount = 3000

출력: 3

예시 4: 그리디 함정 — 6+6이 최소

입력: bills = [[1,10],[6,2],[9,1]], amount = 12

출력: 2

엣지: 요청 금액 0 → 0장

입력: bills = [[1000,3]], amount = 0

출력: 0

엣지: 재고는 넉넉하지만 홀수 금액을 만들 수 없음

입력: bills = [[4,10],[6,10]], amount = 9

출력: -1