[Python] 백준 14916번_거스름돈

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

14916번: 거스름돈

 

• 손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 함
• 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있음
• 동전의 개수가 최소가 되도록 거슬러 주어야 함
• 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주기
• 예를 들어, 거스름돈이 15원이면 5원짜리 3개를
  • 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를
  • 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 함

• 입력
  • 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어짐
• 출력
  • 거스름돈 동전의 최소 개수를 출력
  • 만약 거슬러 줄 수 없으면 -1을 출력
• 시간 제한: 2초
• 메모리 제한: 512 MB

 

"""
입출력 예시)

(예제 입력 1) 
13 -> 5

(예제 입력 2)
14 -> 4
"""

 

 

## 의사코드 ##

# 잔돈은 5원과 2원으로만
# for c in [5, 2]:
#     n = change // c # 필요한 동전의 개수
#     # 남은 거스름돈이 없으면 잔돈 개수 + n 하고 중지
#     if change - (c*n) == 0:
#         cnt += n
#         break 
#     # 남은 거스름돈이 홀수이면 동전 개수 - 1
#     elif change - (c*n) % 2 != 0:
#         n -= 1
#         cnt += n 
#     # 짝수로 나눠 떨어지면 잔돈 개수 + n
#     else:
#         cnt += n
#     change -= c * n # 남은 거스름돈 계산

 

 

 

첫 번째 시도

 

# 거스름돈 
change = int(input())
# 잔돈 개수 
cnt = 0 
for c in [5, 2]:
    n = change // c # 필요한 동전의 개수
    # 남은 거스름돈이 없으면 잔돈 개수 + n 하고 중지
    if change - (c*n) == 0:
        cnt += n
        break 
    # 남은 거스름돈이 홀수이면 동전 개수 - 1
    elif change - (c*n) % 2 != 0:
        n -= 1
        cnt += n 
    # 짝수로 나눠 떨어지면 잔돈 개수 + n
    else:
        cnt += n
    change -= c * n # 남은 거스름돈 계산 
print(cnt)

 

 

-> 틀림 (거슬러 줄 수 없으면 -1 출력해야하는 것 깜빡함)

 

 

 

통과한 코드

 

# 거스름돈 
change = int(input())
# 잔돈 개수 
cnt = 0 

while True:
    # 거스름돈이 5로 나누어 떨어지면 잔돈 개수는 거스름돈을 5로 나눈 수
    if change % 5 == 0:
        cnt += change // 5
        break
    # 5로 나누어 떨어지지 않으면 거스름돈에서 2씩 차감하면서 잔돈 개수 + 1
    else:
        change -= 2
        cnt += 1
    # 거스름돈이 음수가 되면 중지
    if change < 0:
        break
# 거슬러 줄 수 없으면 -1 
if change < 0:
    print(-1)
# 거슬러 줄 수 있으면 잔돈 개수 출력
else:
    print(cnt)

 

 

-> for문으로 5원과 2원을 돌지 않고 5로 나누어 떨어지지 않으면 2원씩 차감하면서 계산

 

 

 

 

 

참고)

 

https://velog.io/@tunaman95/%EB%B0%B1%EC%A4%80-14916%EB%B2%88-%EA%B1%B0%EC%8A%A4%EB%A6%84%EB%8F%88-Python

[백준] 14916번 - 거스름돈 Python