[python] 백준 11047번: 동전 0

https://www.acmicpc.net/user/gurwns876

gurwns876 정보

 

동전 거스름 돈 문제는 그리디 알고리즘에서 유명한 문제이다.

1. 문제 해석
1) 각 동전이 다음 동전이 될 때 n의 배수이므로 큰 숫자부터 차례대로 나누면 된다.
2) 이때 총합 k를 구할 때 동전의 갯수를 구하면 된다.

2. 풀이
1. 동전이 n의 배수이므로 그리디 알고리즘을 사용하면 된다.
2. 처음부터 큰 숫자를 나눈 다음, 몫을 answer에 더하고 나머지를 k에 다시 대입하여 해결한다.
(동전의 n의 배수가 아닐 때는 그리디 알고리즘을 사용하면 안된다. 이 문제도 추후에 풀어보자)

import sys
#sys.stdin = open("input6.txt",'r')
input = sys.stdin.readline
 
n, score = map(int,input().split())
coin_lst = []
for i in range(n):
    coin_lst.append(int(input()))
coin_lst.sort(reverse=True)
 
answer = 0
#각 코인을 나눴을 때 몫이 answer, 나머지가 남은 돈이 된다.
for coin in coin_lst:
    if score >= coin:
        answer += score//coin #몫만큼 더해주기
        score = score%coin #나머지가 거스름돈
        if score <= 0: #0이 되면 반복문 탈출
            break
print(answer)

코테 문제를 매일 안풀다보니 풀때마다 느낌이 새롭다... 간단한 문제라도 1일 1문제는 풀어야겠다.