💰 백준 11047 파이썬: 동전 문제 풀이
https://www.acmicpc.net/problem/11047
동전 문제는 그리디 알고리즘의 대표적인 예제로, 여러 종류의 동전을 사용하여 특정 금액을 만들 때 필요한 _최소 동전 개수_를 구하는 문제입니다. 문제의 핵심 조건과 해결 방법, 그리고 파이썬 코드 구현에 대해 체계적으로 정리하였습니다.
📝 문제 설명 및 조건
1. 기본 문제 개요
– 준규가 가지고 있는 동전은 총 _N종류_이며, 각 동전은 매우 많이 보유하고 있다.
– 동전을 사용하여 가치의 합이 _K원_이 되도록 하는 최소 동전 개수를 구해야 한다.
– 문제의 제약 조건은 _(1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)_이다.
2. 중요 조건
– 동전의 가치 _Ai_는 오름차순으로 주어진다.
– 첫 번째 동전 가치는 항상 _1_이다.
– 중요 포인트: i ≥ 2 인 경우 _Ai_는 _Ai-1_의 배수이다.
– 이 조건으로 인해 그리디 알고리즘으로 해결이 가능하다.
🧩 그리디 알고리즘 풀이 전략
1. 접근 방법
– _Ai_가 _Ai-1_의 배수라는 조건이 그리디 풀이를 가능하게 한다.
– 이 조건이 없으면 반례가 존재할 수 있어 그리디로 풀 수 없다.
– 최적의 선택: 가장 큰 단위의 동전부터 최대한 많이 사용한다.
2. 알고리즘 단계
– 동전 리스트를 내림차순으로 정렬한다.
– 가장 큰 단위부터 차례로 검사하며 사용할 수 있는 최대 개수를 계산한다.
– 사용한 동전 개수를 누적하고, 남은 금액을 갱신한다.
– 남은 금액이 _0_이 되면 종료한다.
💻 파이썬 코드 구현
1. 입력 처리
import sys
input = sys.stdin.readline
n,k = input().split()
n = int(n)
k = int(k)
coins = []
for i in range(n):
coins.append(int(input()))2. 그리디 알고리즘 적용
coins.reverse() # 큰 단위부터 사용하기 위해 리스트 뒤집기
count = 0
for coin in coins:
if k == 0:
break
count += (k // coin) # 현재 동전 단위로 만들 수 있는 최대 개수
k = k % coin # 남은 금액 갱신
3. 결과 출력
print(count) # 사용한 동전의 총 개수 출력🔍 예제 실행 과정
1. 예제 입력 1 (K=4200)
– 동전 단위: 1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000
– 실행 과정:
- 50000원 동전: 사용 불가 (남은 금액: 4200)
- 10000원 동전: 사용 불가 (남은 금액: 4200)
- 5000원 동전: 사용 불가 (남은 금액: 4200)
- 1000원 동전: 4개 사용 (남은 금액: 200)
- 500원 동전: 사용 불가 (남은 금액: 200)
- 100원 동전: 2개 사용 (남은 금액: 0) – 최종 결과: 총 6개 동전 사용
2. 예제 입력 2 (K=4790)
– 동전 단위: 1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000
– 실행 과정:
- 1000원 동전: 4개 사용 (남은 금액: 790)
- 500원 동전: 1개 사용 (남은 금액: 290)
- 100원 동전: 2개 사용 (남은 금액: 90)
- 50원 동전: 1개 사용 (남은 금액: 40)
- 10원 동전: 4개 사용 (남은 금액: 0) – 최종 결과: 총 12개 동전 사용
🌟 핵심 포인트 정리
1. 그리디 알고리즘 적용 조건
– 배수 조건이 그리디 알고리즘의 적용을 가능하게 하였다.
– 이 조건 덕분에 항상 큰 단위 동전을 최대한 사용하는 것이 최적해가 된다.
2. 디버깅 팁
– 알고리즘 문제 해결 시 중간 과정을 출력하는 것이 유용하다.
– 실행 과정에서 변수 값의 변화를 추적하면 문제 해결에 도움이 된다.
pythonprint(f"코인: {coin}, 현재 K: {k}, 사용한 동전 수: {count}")
