[BOJ] 14916번: 거스름돈

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

문제

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

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

 

풀이1: Greedy

사실 처음에는 어떻게 DP로 풀어야 할지 도저히 감이 안 와서, 그냥 그리디로 접근했다..

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

    if n == 0: print(cnt)
    elif n < 0: print(-1)

 

풀이2: DP

다른 분의 블로그를 참고하여 DP를 사용하는 아이디어를 얻을 수 있었다.

예를 들어 13원을 만들기 위해서는 11원에서 +2원, 또는 8원에서 +5원을 하는 이 두 가지의 방법으로만 만들 수 있는 것이다!

n = int(input())
li = [0] * (n + 1)

for i in range(1, n + 1):
    if i == 2 or i == 5:
        li[i] = 1
    else:
        if li[i - 2] and li[i - 5]:
            li[i] = 1 + min(li[i - 2], li[i - 5])
        elif li[i - 2]:
            li[i] =  1 + li[i - 2]
        elif li[i - 5]:
            li[i] = 1 + li[i - 5]
            
print(li[n] if li[n] else -1)

 

이렇게 0으로 리스트를 초기화 한 후, 2와 5를 1로 설정하고 (각각 2원, 5원짜리 동전 한 개로 만들 수 있으므로)

bottom-up 방식으로 n원까지 구하려했는데...

백준에 제출하였더니 100%에서 틀렸습니다 라고 떴다...

확인해보니 n == 3일 때, -1이 출력되어야 하는데 2가 출력되었다. 아마도, i = 3일 때 li[-2]가 li[2]가 되어서 그런 것 같다.

n = int(input())
li = [0] * (n + 1)

for i in range(1, n + 1):
    if i == 2 or i == 5:
        li[i] = 1
    elif i > 3: #조건 추가
        if li[i - 2] and li[i - 5]:
            li[i] = 1 + min(li[i - 2], li[i - 5])
        elif li[i - 2]:
            li[i] =  1 + li[i - 2]
        elif li[i - 5]:
            li[i] = 1 + li[i - 5]
            
print(li[n] if li[n] else -1)

 

i > 3이라는 조건을 추가해서 해결했다. 😹