📝 문제 설명
>
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/11047
🎨 풀이
💡 전체 코드
import sys
n, k = map(int, sys.stdin.readline().split())
money = []
result = 0
for _ in range(n):
money.append(int(input()))
for i in range(len(money)-1,-1,-1):
result += k // money[i]
k = k % money[i]
print(result)
> 핵심 : 큰 동전부터 차례대로 나눠주면 된다. (금액이 큰 동전을 많이 쓸수록 결과가 작아지기 때문)
🍦 코드 설명 (실행 순서대로 나열)
# main
n, k = map(int, sys.stdin.readline().split())
money = []
result = 0
1. n, k를 입력받는다.
- n : 동전 종류 개수
- k : 목표 금액
* 그 외
- money : 동전 종류 리스트
- result : 결과 (필요한 동전 개수의 최솟값)
@ 첫 번째 for문 (3번~5번) => 동전 종류 입력받기
for _ in range(n):
money.append(int(input()))
3. for문을 돌린다. (n만큼)
4. 수를 입력받은 후 money 리스트에 추가해준다.
@ 두 번째 for문 (3번~5번) => 동전 종류 입력받기
for i in range(len(money)-1,-1,-1):
result += k // money[i]
k = k % money[i]
5. for문을 돌린다. (len(money)-1 부터 0까지 하나씩 내려가면서!)
- 이게 가능한 이유는 본문에서 동전 입력을 오름차순으로 한다고 적혀있었기 때문이다.
6. result에 k // money[i] 값을 넣어준다.
- 만약 money[i]가 k보다 크다면 어짜피 0을 더해줄 것이기 때문에 상관없다.
7. k에 k % money[i] 값을 넣어준다.
- 이것도 6번과 같다. 어짜피 나눠준 게 없으면 나머지도 그대로 들어가니까 상관없다. (나눠지면 넣고 아니면 말고~ 이 느낌)
8. result를 출력한다.
끝~
⭐ 느낀점
> 오늘도 열심히 적었다. 오늘은 좀 이해가 되지 않을까 싶긴 하다. 안되면 댓글로 피드백 부탁드림니다. 보는 사람 별로 없겠지만,,~ 감사합니다 ^ㅁ^
'알고리즘 공부 > 백준' 카테고리의 다른 글
[백준] 10872번 - 팩토리얼 (파이썬) (0) | 2022.07.26 |
---|---|
[백준] 1026번 - 보물 (파이썬) (0) | 2022.07.25 |
[백준] 1003번 - 피보나치 함수 (파이썬) (0) | 2022.07.23 |
[백준] 11399번 - ATM (파이썬) (0) | 2022.07.22 |
[백준] 2839번 - 설탕 배달 (파이썬) (0) | 2022.07.21 |