[python 기초] 백준: 11047번 / greedy 알고리즘

📍In a nutshell...

• 탐욕 알고리즘(greedy algorithm)
  • 여러 경우의 수 중, 하나를 선택할 때 그게 최적이라고 생각하고 진행하는 방식
  • 그러나 최적해를 항상 구할 수 있다는 보장은 없음. 따라서, 잘 판단해서 사용해야 함
• 예시 - 거스름돈 문제
  • 거스름돈 800원을 최소의 동전 개수로 손님에게 돌려줘야 한다
  • 500원/400원/100원이 있다고 가정할 때, 최적해는 400원 2개를 주는 것이지만 탐욕 알고리즘을 잘못 사용하면 500원 1개 + 100원 3개, 총 4개를 주는 것으로 계산할 수 있다
  • 하위 level의 동전이 상위 level의 동전의 배수인지가 key
    : 탐욕적 선택은 항상 안전하다는 탐욕 알고리즘의 필수 요소 충족

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

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

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

풀이)

N, K = map(int, input().split())

coin = []
for _ in range(N):
    coin.append(int(input()))

cnt = 0 

for i in reversed(range(N)):
    cnt += K//coin[i]
    K = K%coin[i]

print(cnt)

• 주어지는 coin은 하위 coin의 배수
  • 내림차순 적용하여, 탐욕 알고리즘적 접근 가능
  • 상위 coin으로 최대한 처리하는 것이 최적해임이 보장됨
• 주어진 동전을 coin에 담고, 내림차순한다(reversed())
• 동전의 개수를 계산할 cnt 를 선언한다
• 역순시켜 차례대로 개수 계산
  • K(금액)//coin[i] : 나누기해서 나온 몫이 개수
  • K%coin[i] : 나머지를 K에 담고, 하위 coin으로 재계산

참고 자료
백준