백준(baekjoon) 11047번: 동전 0(실버 4, 파이썬 PYTHON) - 그리디 알고리즘

문제

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

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

 

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

11047번: 동전 0

 

import sys

N,K=map(int,sys.stdin.readline().split())
coin=[int(sys.stdin.readline()) for _ in range(N)]
count=0

for x in range(N-1,-1,-1):
  if(K==0):
    break
  if(K<coin[x]):
    continue
  else:
    how_many=K//coin[x]
    K-=coin[x]*how_many
    count+=how_many

print(count)

 

※ 그리디 알고리즘

 

 

● 먼저 N과 K를 입력받는다. 그 후 N개의 줄에 나오는 동전의 가치들을 coin이라는 배열에 저장해주고, 필요한 동전 개수의 최솟값을 계산할 초기값 0인 변수 count를 정의해준다.

 

● 동전을 최소한으로 사용하여 K값을 만들려면 가장 단위가 큰 동전부터 우선적으로 사용하여 값을 채워 나가야한다. x가 N-1부터 0까지 감소하는 for문을 하나 만들어준다. for문 안에서 만약 동전들을 사용하여 K값을 다 만들었다면 (K==0) 루프를 빠져나간다. 

 

● 아직 값을 더 채워야하고 현재 보고 있는 동전 단위가 채워야 할 값보다 크다면 (K<coin[x]) 이 동전을 사용할 수 없으므로 continue를 사용하여 for문으로 돌아가준다. 아직 값을 더 채워야하고 현재 보고 있는 동전 단위가 채워야 할 값보다 작으면 이 동전을 이용하여 남은 K값을 최대한 채워준다. 현재 K 값을 이 동전 단위로 나눈 몫이 이 동전을 사용할 수 있는 최대 개수를 나타내므로 how_many에 이 값을 넣어준 뒤 how_many 값을 count에 더해주고, how_many를 이 동전 단위와 곱한 값 즉, 이 동전을 사용하여 채운 액수를 K에서 빼준다.

 

● K값을 다 채워 for문을 빠져나왔다면, count값을 출력해주면 답을 구할 수 있다!