[dp] 백준 14916 파이썬

백준 14916번 거스름돈 dp 풀이입니다.

greedy 알고리즘으로 푸는 방법도 있지만, dp로도 분류되어 있어서 dp로 간단하게 풀어보았습니다.

---

[문제]

[과정]

처음엔 5로 나누어 떨어질 때, 2로 나누어 떨어질 때 등의 상황을 if문으로 적절하게 구성해서 구현해보려 했습니다.

점점 greedy 알고리즘으로 구현하게 되어, 이전 index에 저장될 값을 어떻게 이용해볼까 생각하다가

그냥 경우의 수를 쭉 작성해보았습니다. 

 

[풀이]

2원짜리 동전은 최대한 적게 사용해야 하고, 5원짜리 동전은 최대한 많이 사용해야 합니다.

작성하다 보면 2원짜리 동전은 5개 이상은 사용할 필요가 없다는 걸 알 수 있습니다.

또 추가적으로 답이 -1인 경우는 n이 1일 때와 n이 3일 때밖에 존재하지 않습니다.

간단히 생각해보면,

3 이상의 짝수는 모두 2로 나눠질 것이고, 3 이상의 홀수는 5로 한 번 빼주기만 하면 모두 짝수가 될 수 있습니다. 그럼 이 수는 또 2로 나눌 수 있습니다. 따라서 3 이후로는 5와 2를 어떻게 조합해서 만드냐의 문제가 됩니다.

 

이렇게 쭉 작성해 보면,

2원짜리 동전의 개수는 똑같은 패턴이 반복되고,

5원짜리 동전은 다섯 번째 이전의 dp 값에서 하나만 더 사용해주면 되는 것을 알 수 있습니다.

따라서 dp[i-5] + 1 (i >= 10)이라는 간단한 점화식을 세울 수 있습니다.

규칙은 10번째에서부터 적용되므로 10번째까지는 그렇게 귀찮지 않으니 직접 값을 지정해주었습니다.

 

[python 구현]

n = int(input())
dp = [-1, -1, 1, -1, 2, 1, 3, 2, 4, 3]
for i in range(10,n+1):
    dp.append(dp[i-5]+1)

print(dp[n])