[백준] 11047 : 동전 0 (Python/파이썬)

문제 링크

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

문제

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제

입력

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

출력

6

---

정답 및 풀이

import sys
input = sys.stdin.readline

n,k = map(int,input().split())

nlist=[]
cnt=0

for _ in range(n):
    i = int(input())
    nlist.append(i)

for i in range(len(nlist)-1,-1,-1):
    if nlist[i] <= k:
        cnt += k//nlist[i]
        k = k%nlist[i]

print(cnt)

1. import sys
   • sys 모듈을 불러와 빠른 입력 처리를 하기 위함이다.
2. input = sys.stdin.readline
   • 기본 input 보다 빠른 stdin 입력을 사용하기 위해 재정의한다.
3. n,k = map(int,input().split())
   • 동전의 개수 n 과 목표 금액 k 를 입력받는다.
4. nlist=[]
   • 동전의 금액들을 저장할 리스트를 생성한다.
5. cnt=0
   • 필요한 동전의 총 개수를 저장할 변수를 초기화한다.
6. for _ in range(n):
   • 동전의 개수 n 만큼 반복한다.
7. i = int(input())
   • 각 동전의 금액을 하나씩 입력받는다.
8. nlist.append(i)
   • 입력받은 동전 금액을 리스트에 저장한다.
9. for i in range(len(nlist)-1,-1,-1):
   • 동전 리스트를 가장 큰 값부터 작은 값 순서로 순회한다.
   • 그리디 알고리즘의 핵심으로, 큰 동전부터 사용하는 방식이다.
10. if nlist[i] <= k:
    • 현재 동전이 남은 금액 k 보다 작거나 같을 때만 사용한다.
11. cnt += k//nlist[i]
    • 현재 동전으로 사용할 수 있는 최대 개수를 구해 cnt 에 더한다.
12. k = k%nlist[i]
    • 해당 동전으로 사용하고 남은 금액으로 k 를 갱신한다.
13. print(cnt)
    • 목표 금액을 만들기 위해 사용한 최소 동전 개수를 출력한다.

---

핵심 개념

• 그리디 알고리즘
  • 매 순간 가장 좋아 보이는 선택을 하는 알고리즘