다양한 화폐 단위가 주어졌을 때 n원을 만들 수 있는 경우의 수를 구하는 문제다.
n원을 만들기 위한 경우의 수를 구해야 하므로, "큰 문제를 작은 문제로 나눈다"는 컨셉으로 접근할 수 있다.
따라서 DP 문제다. (DP 정리 : gaza-anywhere-coding.tistory.com/117)
화폐의 작은 단위부터 만들 수 있는 금액의 경우의 수를 구해나간다.
밑에 적은 표를 보면, 1원과 2원으로 4원을 만들 수 있는 경우의 수는 3이다.
1원을 이용해서 4원을 만들 수 있는 방법 : 1가지 (1원+1원+1원+1원)
+
2원을 이용해서 4원을 만들 수 있는 방법: 2가지 (1원+1원+2원), (2원+2원)
>>> 4(price) - 2(unit) = 2이므로, 2원을 만들기 위한 경우의 수를 리스트에서 찾고, 기존에 4원을 만들 수 있는 경우의 수를 적었던 리스트의 원소 값에 더해준다.
코드 참고
[Python] 프로그래머스 - 거스름돈 (연습문제/DP)
📃 문제 링크Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다.예를 들어
velog.io
'코딩 테스트' 카테고리의 다른 글
| [스택][프로그래머스] 괄호 회전하기 (0) | 2021.04.26 |
|---|---|
| [DP][백준, 12865] 평범한 배낭 (0) | 2021.04.23 |
| [그리디][백준, 1027] 토너먼트 (0) | 2021.04.20 |
| [DFS][백준, 4963] 섬의 개수 (0) | 2021.04.20 |
| [구현][백준, 14719] 빗물 (2) | 2021.04.19 |