Baekjoon 14916 | 거스름돈 (Python)

📌문제

SILVER5 / DP / 그리디 / 수학

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

 

📌문제 분석 및 설계

처음에는 생각없이 아 걍 5로나누고 2로 나누면 되는 문제네~ 하고 코딩했더니 바로 틀려서 엥? 했다가

아무래도 동전의 개수가 최소가 될려면 5가 많아야된다고 생각해서 거스름돈을 5로나는 몫을 구해 점점 줄여가는 식으로 계산했다.

 

1. 거스름돈을 5로 나눈 몫 구하기

2. 1번에서 구한 값에서 시작해서 줄여가며 즉, 5원 개수를 줄여가며 나머지를 2로 나눴을 때 0이 될때까지 반복

3. 0이 안되면 -1 출력 

 

문제를 푼 후 다른 사람들의 풀이를 보니 DP로도 풀던데... 난 아직 DP를 생각해내기 너무 어렵다.. ㅠ

 

📌소스 코드

n=int(input())
result=-1
for i in range(n//5,-1,-1):
    temp=n-(i*5)
    if temp%2!=0:
        continue
    else:
        result=i+(temp//2)
        break
print(result)