[백준] - 2839. 설탕 배달(python)

[dp - bottom up + dp table 문제풀이]

n = int(input())
dp = [10000] * (n+5)

dp[3] = dp[5] = 1

for now in range(6, n+1):
    dp[now] = 1 + min(dp[now-3], dp[now-5])

print(dp[n] if dp[n] < 10000 else -1)

10000	10000	1	10000	1	2	10001	2	3	2
1	2	3 / 3	4	5	6	7	8	9	10

• 6의 경우
  • 6부터 살펴보는 이유는 간단하다 3과 5 이후의 숫자만 설탕을 나눌수 있기 때문이다. 
  • 3(6-3)의 경우엔 1개의 설탕이 저장되어 1을 더해주면 최종적으로 6kg의 설탕을 3kg 2개로 나눌 수 있게 된다.
  • 1(6-5)의 경우엔 10000이라는 수가 저장되어 1을 더해주면 최종적으로 10001이라는 수가 나와서 더 작은 수인 2가 최종적으로 6kg엔 저장되게 된다.
• 7의 경우
  • 해당 수는 5와 3으로 나눠서 사용할 수 없기 때문에 2, 4의 10000에서 1을 더한 10001이 최소의 수여서 넘어간다.
• 8의 경우
  • 3과 5 어떤 수가 와도 최소 2개로 옮길 수 있게 됨 이때 2를 저장 해준다.

dp와 반복문 그리고 dp table?

- dp 문제에서 반복문을 사용하면 bottom up 방식을 사용한다하고 이때 중복되는 값들을 dp table에 저장해서 중복 값은 메모리에서 불러오는 방식을 사용한다. 

- 이때 dp table은 배열(파이썬에선 리스트)을 사용해도 괜찮고 해쉬테이블(파이썬에서는 딕셔너리)를 사용해도 괜찮다.