[Python] 백준 #14916- 거스름돈

문제

---

14916번: 거스름돈

코드

---

My answer

charge=int(input())

answer=0
for i in range(charge//5,0,-1):
    if((charge-(5*i))%2==0):
        answer=i+(charge-(5*i))//2
        break
if(answer==0):
    if(charge%2==0):answer=charge//2
    else:answer=-1

print(answer)

import sys
input=sys.stdin.readline

n=int(input())

dp=[0,0,1,0,2,1]+[0 for _ in range(n+1)]

for i in range(6,n+1):
    if(dp[i-5]!=0 and dp[i-2]!=0):
        dp[i]=min(dp[i-2]+1,dp[i-5]+1)
    elif(dp[i-5]==0):
        dp[i]=dp[i-2]+1
    else:
        dp[i]=dp[i-5]+1
if(dp[n]==0):print(-1)
else:print(dp[n])

Another answer

n = int(input())
dp = [-1]*(n+1)
dp[0] = 0
for i in range(1, n+1):
    if i >= 2 and dp[i-2] > -1:
        dp[i] = (dp[i-2]+1) if dp[i] == -1 else min(dp[i-2]+1, dp[i])
    if i >= 5 and dp[i-5] > -1:
        dp[i] = (dp[i-5]+1) if dp[i] == -1 else min(dp[i-5]+1, dp[i])
print(dp[n])

import sys 
input=sys.stdin.readline 

n = int(input()) 
num = n%5 
count = 0 
if n==1 or n==3 : 
    print(-1)
elif num%2==0 : 
    print(n//5 + num//2)
else :
    print((n//5)-1 + (num+5)//2)
exit(0)

풀이

---

내 풀이 1: 그리디 방식 해결 5와 2로 구성되야 하므로,

1. 5로 나눠지고 2로 나눠떨어지지 않으면 패스, 5로 나눠지고 2로 나눠 떨질떄만 이후 진행 

-> 5로 나눴을 때의 몫, 5로 나눈 나머지를 2로 나눴을 때의 몫

2. 5로 안나눠졌거나, 5로 나눠졌는데 나머지가 2로 나눠지지 않을 경우 

-> 전부 2로 나누거나, 반환 불가 

 

내 풀이 2번: 동적계획법으로 해결(추후 수정)

 

다른 풀이 1번: 동적계획법으로 해결(추후 수정)

 

다른 풀이 2번: n이 1이거나 3인 경우를 제외하고는 모두 2와 5로 만들 수 있음. 이 두 경우만 제외하고 나머지는 위와 동일한 방식

중요한 건 1,3을 제외하고는 모두 구성할 수 있기 때문에 5로 나눠지고, 2로 나눠떨어지지 않는 경우 5로 나눈 몫에서 1을 빼주고, 원래 5로 나눴던 나머지(2로 나눠떨어지지 않는 홀수)에다가 5를 더해주면 반드시 2로 나눠짐.