[그리디 1] 거스름돈

0. 그리디란?

그리디 = 탐욕법 = 가장 좋은 것을 선택한다. 그러므로 미래는 고려하지 않는다.

따라서 가장 좋은 것을 선택하여도 문제를 풀 수 있는지 확인하는 것이 중요하다. 그리디는 가장 큰 순서대로, 가장 작은 순서대로 등 알게 모르게 기준을 제시한다. 그런 경우 정렬과 함께 등장하는 경우도 있기 때문에, 정렬을 이용하는 경우도 있을 수 있다.

아래와 같은 거스름돈 문제는 대표적인 그리디 문제이다.

1. 문제 설명하기.

카운터에는 500원, 100원, 50원, 10원짜리 동전이 있다. 그리고 동전은 무한히 존재한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

2. 문제 풀이하기.

가장 화폐 단위가 큰 돈부터 거슬러 주는 것이다. 예를 들어 1260원을 거슬러줘야 한다면 500원 x 2개+100원 x 2개+50원 x 1개+10원 x 1개로 나타낼 수 있다. 그러므로 최소 개수는 2+2+1+1=6개이다.

# 거스름돈이 1260원인 경우

n=1260
count = 0 # 거스름돈의 최소 개수
count_type=[500, 100, 50, 10]

for coin in count_type:
    
    """
    [변수 설명하기]
    print(coin)
    print(n//coin) # 나누어지는 코인의 개수
    print(n%coin) # 큰 수로 나눈 후 남은 코인
    """
    
    count+=n//coin
    # n=n%coin : 밑에 있는 코드와 동일한 코드이다.
    n%=coin

print(count)

일반화를 시킬 수 있다.

# 거스름돈을 일반화시킨 경우

n=int(input("거스름돈을 입력해주세요."))
count = 0 # 거스름돈의 최소 개수
count_type=[500, 100, 50, 10]

for coin in count_type:
    
    """
    [변수 설명하기]
    print(coin)
    print(n//coin) # 나누어지는 코인의 개수
    print(n%coin) # 큰 수로 나눈 후 남은 코인
    """
    
    count+=n//coin
    # n=n%coin : 밑에 있는 코드와 동일한 코드이다.
    n%=coin

print(count)

3. 그리디 알고리즘의 정당성

모두 그리디 방식을 풀 수 있는 것은 아니다. 하지만, 탐욕적으로 풀이하였을 때 문제를 해결할 수 있다면 효과적인 문제 풀이 방법이 될 수 있다.

거스름돈 문제라고 항상 위와 같이 풀이할 수 있는 것은 아니다. 만약에 거스름돈 중에서 작은 단위의 수가 큰 단위의 약수인 경우 위와 같이 풀이할 수 없다.

예를 들자면 거스름돈이 500원, 200원, 100원, 50원, 10원인 경우이다. 200원은 100원 2개로 만들 수 있다. 1260원을 500원 x 2개+200원 x 1개+50원 x 1개+10원 x 1개이다. 따라서 최소 단위의 개수는 2+1+1+1=5개이다. 200원을 먼저 고려한 뒤에, 100원을 고려하는 방식으로 코드를 제작해야 한다.

# 거스름돈이 1260원이고, 
# 거슬러주는 돈이 500원, 200원, 100원, 50원, 10원인 경우

n=1260
count=0
coin_type=[500, 200, 100, 50, 10]

for coin in coin_type:
    if (coin%500==0) or (coin%200==0):
        count+=n//coin
        n%=coin
        
for remain_coin in coin_type[2:]:
    count+=n//remain_coin
    n%=remain_coin
    
print(count)

일반화 시킬 수 있다.

# 거스름돈을 일반화, 
# 거슬러주는 돈이 500원, 200원, 100원, 50원, 10원인 경우

n=int(input("거스름돈을 입력해주세요.")) # 1840원 입력한 경우
count=0
coin_type=[500, 200, 100, 50, 10]

for coin in coin_type:
    if (coin%500==0) or (coin%200==0):
        count+=n//coin
        n%=coin
        
for remain_coin in coin_type[2:]:
    count+=n//remain_coin
    n%=remain_coin
    
print(count)

값을 확인해보자. 1840원은 500원 x 3개+200원 x 1개+100원 x 1개+10원 x 4개이다. 따라서 3+1+1+4=9개이다. 제대로 답이 도출되었다.