[BJO] 14916번 - 다이내믹 프로그래밍

거스름돈 성공

2 초

512 MB

25175

11674

9706

47.254%

문제

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

손님이 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을 출력한다.

예제 입력 1 

13

예제 출력 1 

5

예제 입력 2 

14

예제 출력 2 

4

 

Try1) 그리디 알고리즘

사실 맨처음에는 가장 간단하게 5로 가져갈 수 있는거 다 가져가고, 남은거 2로 가져가는데 홀수로 남으면 5코인 하나 포기해서 +5로 짝수로 만든 다음에 //2로 몫 계산해서 더하는 방식을 선택했다.

n=int(input())

if n==1 or n==3:
    print(-1)
elif (n%5)%2==0:
    five = n//5
    two = n%5//2
elif (n%5)%2==1:
    five=n//5-1
    two=(n%5+5)//2

print(five+two)

예제도 맞고 코드 자체에는 문제가 없었으나 문제의 의도가 이게 아니었기 때문에 런타임에러로 실패!

이후 다이내믹 프로그래밍에 맞춰서 짜는 법을 고민했고 동전갯수에 규칙을 찾고자 했다.

 

Try2) Answer 

입력한 n 값	필요한 5코인 개수	필요한 2코인 개수
1	-	-
2	0	1
3	-	-
4	0	2
5	1	0
6	0	3
7	1	1
8	0	4
9	1	2
10	2	0
11	1	3
12	2	1
13	1	4
14	2	2

 

처음에는 큰 규칙이 없어보이는 듯 싶으나 5~9, 10~14 이렇게 5단위로

5코인은 10101, 21212, ...

2코인은 03142가 반복되는 것은 확인할 수 있다.

따라서 배열을 만들어 미리 5~9일때 필요한 코인개수를 저장해두고

이후 들어오는 n값에 따라 추가되는 +값만 계산하여 바로 출력할 수 있도록 코드를 짰다.

n=int(input())

dp=[0]*5
dp[0]=0
dp[1]=2
dp[2]=1
dp[3]=3
dp[4]=2

if n==1 or n==3 :
    print(-1)
elif n==2:
    print(1)
elif n==4:
    print(2)
else:
    print(dp[n%5]+n//5)