[알고리즘/그리디] 14916번 : 거스름돈 - python

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

14916번: 거스름돈

 

---

• 문제
• 소요시간: 7분 35초

---

• 설계하기(접근방법) 

1. 입력받기

거스름돈을 입력받는다

 

2. 구현하기

 

수학적으로 접근했다. 둘의 최소공배수인 10을 넘어가는 경우, 거스름돈을 거슬러주지 못하는 경우는 없으므로 10 아래의 경우의 수만 고려해서 while문을 돌렸다. 

 

1,3 인 경우 거슬러줄 수 없고

2,4,6,8인 경우 각각 1,2,3,4,를 몫으로 동전 개수에 더해준다

5, 7, 9 혹은 그 이상은 while문으로 반복하면서 개수를 구할 수 있다

 

3. 출력하기

동전의 개수를 출력한다

 

 

 

 

---

• 코드(출력)

n = int(input())

cnt = 0 

while True:
    if n == 1 or n == 3:
        cnt = -1
        break
    if n == 8:
        cnt += 4
        break
    if n == 6:
        cnt += 3
        break
    if n == 4:
        cnt += 2
        break
    if n == 2:
        cnt += 1
        break
    if n == 0:
        cnt += 0
        break
    n -= 5
    cnt += 1

print(cnt)

 

더 좋은 코드

n= int(input())
cnt = 0

while n > 0:
    if n % 5 == 0 :
        cnt += (n //5)
        break
    n -= 2
    cnt += 1
    
if n < 0 :
	print(-1)
else:
	print(cnt)

---

• 얻어갈 부분

1. greedy로 5로 나누어질 때까지 2를 빼주고, 나누어지면 cnt를 출력하고

만약 나누어지지 않는다면 -1로 출력하는 방법을 사용하면 좀 더 코드를 간결하게 짤 수 있다