BOJ 14916 - 거스름돈 (Python3)

수학적으로 접근할 수 있는 문제는 먼저 수학으로 접근해 보아야 한다. 런타임 전의 전처리를 뇌로 하는 것이다.

인간의 뇌라고 특별할 게 있겠는가. 돌발상황에 아주 잘 대처하는 거대한 생체 컴퓨터인 것을.

머리로 계산하고 코드를 단순히 짜는 게 오히려 더 낫다(고 한다). 주석만 적당히 달려 있다면.

물론 기본기가 어느 정도 되어 있다는 전제 하에 말이다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

춘향이는 편의점 카운터에서 일한다.

손님이 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
13

# 예제 출력 2
14

 

출력

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

 

예제 출력)

# 예제 출력 1
5

# 예제 출력 2
4

 

---

내 코드

n = int(input())
if n in (1,3): print(-1)
else:
    if n%5==0: print(n//5)
    elif n%5==1: print((n-6)//5+3)
    elif n%5==2: print(n//5+1)
    elif n%5==3: print((n-8)//5+4)
    else: print(n//5+2)

 

우선 최소로 동전 갯수를 줘야 하니 가능한 한 5원짜리 동전을 많이 줘야 한다. 2원짜리는 남은 것을 메꾸는 용도로만 주는 것으로.

일단 짝수와 짝수+5 꼴의 수(=5 이상의 홀수)는 어떻게든 2원과 5원짜리로만 낼 수 있다. 그러니 2원과 5원으로 거슬러 줄 수 없는 액수는 1원과 3원. 먼저 그 두 개만 걸러 준다.

그 다음, 5로 나눈 나머지를 통해서 다섯 가지로 분류하자. 당연히 5의 배수면 5원짜리로만 주면 된다.

5의 배수+2꼴이면 2원 하나에 나머지를 5원으로, 5의 배수+4꼴이면 2원 두 개에 나머지를 5원으로 주면 될 테고.

 

5의 배수+1꼴이면, 우선 1원은 애초에 지불 불가했으니 빼고. 6원을 2원짜리로, 나머지를 5원짜리로 주면 될 것이다.

5의 배수+3꼴이면 마찬가지로 8원을 2원짜리로 주고 나머지를 5원짜리로 주면 될 것.

그대로 코드를 짜면 그만이다. 다이나믹 프로그래밍으로 풀 수도 있겠으나, 이 편이 훨씬 간편하고 좋겠지.

 

이로서 14916번의 풀이를 마친다.

그럼, 오늘도 당신의 코딩 실력이 상승하기를.