[Python] 백준 #2839- 설탕 배달

문제

---

2839번: 설탕 배달

코드

---

My answer

import sys
input = sys.stdin.readline

n=int(input())

dp=[-1]*(n+1)
sugar=[3, 5]

for i in range(3,n+1):
    if(i==3 or i==5):dp[i]=1
    for j in sugar:
        if(dp[i-j]!=-1):
            if(dp[i]==-1):dp[i]=dp[i-j]+1
            else:dp[i]=min(dp[i-j]+1,dp[i])
print(dp[n])

Another answer

num = int(input())
count = 0

while num >= 0:
  if num % 5 == 0:
    count += int(num // 5)
    print(count)
    break
  
  num -= 3
  count += 1
  
else:
  print(-1)

풀이

---

나는 dp를 이용해서 문제를 풀었다. 얼마 전 풀었던 [이것이 취업을 위한 코딩 테스트다] 예제 문제에서 풀었던 문제라, 쉽게 해결할 수 있었다. 아이디어는 간단하게 이전에 만든 무게에다가 3 혹은 5를 빼서 만들 수 있으면 1을 올려주는 방식이다. 

우선 전부 -1로 초기화를 해두고, 3,5kg의 경우는 한번으로 가능하므로 미리 1로 초기화를 해둔다. 

이후 i에서 sugar에 있는 3,5를 빼면서 만약 dp[i-j]를 만드는 것이 가능한데 여기다가 3 혹은 5를 더하면 당연히 이번 dp[i]도 만들 수 있는 것이기 때문에 dp[i-j]에다가 1을 더해준다. 이 때 예를 들어 3을 더해서도 만들 수 있고, 5를 더해서도 만들 수 있을 때 그 땐 최소값을 선택해야 한다. 예를들어 dp[15]의 경우, dp[12]에다가 3을 더해도 되고, dp[10]에다가 5를 더해도 되는데 이런 식으로 -1이 아니라 이미 값이 존재할 떈 비교해서 넣어주면 된다. 

효율적인 화폐 구성-[이것이 취업을 위한 코딩 테스트다]