[백준] 11047번 - 동전 0 (파이썬)

📝 문제 설명

>

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

입출력 예시

 

https://www.acmicpc.net/problem/11047

11047번: 동전 0

---

🎨 풀이

💡 전체 코드

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를 출력한다.

---

​끝~

 

⭐ 느낀점

> 오늘도 열심히 적었다. 오늘은 좀 이해가 되지 않을까 싶긴 하다. 안되면 댓글로 피드백 부탁드림니다. 보는 사람 별로 없겠지만,,~ 감사합니다 ^ㅁ^