[백준 - 11047][Python] 동전 0

안녕하세요. 성조입니다.

이 포스팅은 Python 3 버전을 기준으로 풀이됐습니다.

동전 문제가 종종 보이는 것 같습니다.

이 문제는 그리디 알고리즘을 기반으로 만들어진 문제입니다.

 

 

문제 출처

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

11047번: 동전 0

---

문제

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

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

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

코드

import sys

N, K = map(int, sys.stdin.readline().split())

coin = []
cnt = 0

for i in range(N):
    coin.append(int(sys.stdin.readline()))

coin.sort(reverse=True)

for money in coin:
    cnt += K // money
    K %= money
print(cnt)

 

풀이

1. 동전 종류를 입력받을 N개와 돈인 K를 map 함수를 통해 한 줄에 입력받는 코드를 구현한다.

2. 리스트에 [1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000]를 차례대로 입력받는다. [오름차순 입력이 필요하다.]

3. 내장 함수인 sort를 활용하여 역순으로 만든다.[내림차순으로 만든다.]

4. coin 리스트의 맞게 money 리스트로 coin의 값에 있는 리스트 들을 큰 값부터 (내림차순 해놨기 때문.) K랑 나눗셈 연산자 //로 나눌 수 있는 횟수를 cnt 변수에 대입한다.

5. % 연산자를 활용해서 K가 money 값에 나눠졌다면 K에서 money 값을 제외한다.  

6. cnt를 출력한다. [개수]

 

 

---

오타나 이해가 안 가는 부분이 있다면 언제든지 댓글로 얘기해 주시면 감사드리겠습니다.

 

부족한 실력이지만 언제든지 효율적으로 구현할 수 있는 피드백 방향을 주시면 많은 참고 진행하겠습니다.

 

다음 포스팅 때 뵙겠습니다!