[TIL] 99클럽 코테 스터디 14일차 TIL - 그리디 : <백준 14916 거스름돈> 문제 풀이 with python

Today's keyword : 그리디

 

📌 문제설명

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

 

📌 문제풀이

"거스름돈"은 주어진 금액을 최소한의 동전 개수로 거슬러 주는 방법을 찾는 문제입니다. 사용 가능한 동전은 2원과 5원짜리로, 이 동전들만으로 정확히 주어진 금액을 만들 수 있어야 합니다. 만약 정확히 거슬러 줄 수 없다면 -1을 출력해야 합니다.

내가 푼 코드

n = int(input())
count = 0
# 5원으로 크게 나누고 안 나눠지면 5원의 개수를 줄임. 
five = n//5  # 5원 동전 개수 
two = 0  # 2원 동전 개수 
while True: 

    remain = (n - (5*five) - (2*two))
    
    if five < 0: 
        print(-1)
        break
        
    # 거스름돈이 남지 않았을 때 최종 동전 개수 출력 
    if remain == 0 : 
        print(five+two) 
        break 
    # 남은 돈이 2원으로 나눠지지 않을 때 5원의 개수를 줄임
    if remain%2 == 1: 
        five -= 1
    else: 
        two = remain//2

다른 정답 코드 

N = int(input())

# 초기화
count = 0

while N > 0:
    # 5로 나누어 떨어지면 5원 동전 최대한 사용
    if N % 5 == 0:
        count += N // 5
        N = 0
    else:
        # 5로 나누어 떨어지지 않으면 2원을 하나 사용하여 남은 금액 줄이기
        N -= 2
        count += 1

# 정확하게 거슬러 줄 수 있는 경우
if N == 0:
    print(count)
# 거슬러 줄 수 없는 경우
else:
    print(-1)

이 문제는 그리디 알고리즘의 대표적인 예제 중 하나로, 최적의 선택을 반복하여 전체 문제의 최적해를 구하려 합니다. 여기서 그리디 접근 방식은 큰 단위의 동전 (5원)부터 최대한 사용해 나가는 것입니다.

거스름돈 동전의 최소 개수를 출력하는 문제이기 때문에 '2원' 짜리 동전과 '5원' 짜리 동전 중 최소가 되도록 '5원'을 우선적으로 거슬러 줍니다. 하지만, 5원을 최대 개수로 거슬렀을 때 남은 돈이 홀수가 되게 되면 '2원' 으로는 거슬러 줄 수 없으므로 5원의 동전 개수를 줄여 남는 돈이 0이 되도록 맞춥니다. 

1. 5원 동전 최대한 사용: 먼저 주어진 금액 n에서 5원 동전을 최대한 사용하여 남은 금액을 줄입니다.
2. 2원 동전으로 나머지 처리: 5원 동전으로 나눈 나머지가 2원으로 나눠떨어지면, 2원 동전만 추가로 사용해서 최소 동전 개수를 구할 수 있습니다.
3. 예외 처리: 5원 동전으로 나눈 나머지가 2원으로 나눠떨어지지 않는 경우, 5원 동전 사용량을 하나씩 줄여가며 나머지를 2원 동전으로 채울 수 있는지 확인합니다.

 

📌 오늘의 회고 

간단한 문제여도 효율성 있게 코드를 짜자

 

 

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL