[백준] [DP] 17212. 달나라 토끼를 위한 구매대금 지불 도우미

17212. 달나라 토끼를 위한 구매대금 지불 도우미

17212번: 달나라 토끼를 위한 구매대금 지불 도우미

 

• 내 풀이
  • 0일때 처리해줘야함

#1,2,5,7
# 동전개수 최소
n=int(input())

mlst=(1,2,5,7)
dp=[1 if i in mlst else int(1e9) for i in range(n+1)]
dp[0]=0
for m in mlst:
    for i in range(m,n+1):
        if i%m==0:
            dp[i]=min(dp[i],i//m)
        else:
            dp[i]=min(dp[i], dp[m]+dp[i-m])

print(dp[n])

 

• 나눠질때 처리하면 조금 더 빠르긴 한데 없어도 가능

#1,2,5,7
# 동전개수 최소
n=int(input())

mlst=(1,2,5,7)
dp=[1 if i in mlst else int(1e9) for i in range(n+1)]
dp[0]=0
for m in mlst:
    for i in range(m,n+1):
        dp[i]=min(dp[i], dp[m]+dp[i-m])

print(dp[n])