방구석프로의 이야기

https://www.acmicpc.net/problem/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)