백준 알고리즘 2839: 설탕 배달(Python)

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

2839번: 설탕 배달

---

문제 해결을 위한 과정

이 문제는 dp를 이용하면 쉽게 해결할 수 있었습니다. 우선 dp 테이블을 만들고 최댓값으로 초기화해줍니다. 이후 해당하는 인덱스가 설탕으로 만들 수 있는 무게인지를 확인합니다. 이를 점화식으로 작성하면 다음과 같습니다.

 

dp [i] = min(dp[i], dp[i-설탕] + 1)

 

이를 소스코드로 작성하면 다음과 같습니다.

---

소스코드

bags = [3, 5]
n = int(input())
INF = int(1e9)
dp = [INF] * 5001
dp[0] = 0

for i in range(len(bags)):
  for j in range(5001):
    if j - bags[i] >= 0:
      dp[j] = min(dp[j], dp[j-bags[i]] + 1)

if dp[n] != INF:
  print(dp[n])
else:
  print(-1)