백준 14916번 파이썬 _ 거스름돈

www.acmicpc.net/problem/14916

14916번: 거스름돈

문제유형 : 수학, DP

문제풀이 :

 

 

정답코드 :

1. 내가푼코드 (DP 로품, 근데 걍 빨리 풀고싶어서 좀 안좋게품 호호 _ 메모리낭뷔, 그래도 편법은 아니지않나? )

import sys
input = sys.stdin.readline

n = int(input())

dp = [-1] * (n+8)

dp[2]=1
dp[4]=2
dp[5]=1
dp[6]=3
dp[7]=2
dp[8]=4

for i in range(9, n+1):
    dp[i] = min(dp[i-2], dp[i-5])+1

print(dp[n])

2. 다른분 코드 ( DP말고 수학적으로 접근하신듯 _ 나보다좋다)

n = int(input())

cnt = 0
i = 0
while True:
    if n % 5 == 0:   # 5의배수이면 or 2로만 거슬러주고 n이 0이된경우 
        cnt += n//5		#5로나눈 몫이 정답 
        break
    else:
        n -= 2   #5의배수가 아니면 2백원씩 뺴면서 5로 나누어떨어지는것이 나오도록
        cnt += 1

    if n < 0:  # 2백원씩 뺏더니 음수가 되버린경우 --> 거슬러줄수 없을을 의미함 
        break
if n<0:			# 음수면 거슬러줄수없 
    print(-1)			
else:
    print(cnt)