그리디 알고리즘: 거스름돈 문제

가장 큰/작은 거 순차 선택하는 문제에 사용할 수 있다.

 

거스름돈 문제 코드)

n = int(input()) 	#금액
count = 0

list = [1000, 500, 100, 50, 10]

for coin in list:
	count += n //coin 	#해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
	n %= coin		#나머지로 리셋

print(count)

 

큰 수의 법칙)

n, m, k = map(int, input().split())
data = list(map(int, input().split()))
             
data.sort()
max1 = data[n-1]
max2 = data[n-2]

result = 0

while True:
    for i in range(k):
        if m == 0:
            break
        result += max1
        m -= 1
    if m == 0:
        break
    result += max2
    m -= 1
    
print(result)