[백준] 2839번: 설탕배달 | 파이썬

알고리즘 분류: 그리디 알고리즘(Greedy) | 다이나믹 프로그래밍

 

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

2839번: 설탕 배달

 

내 풀이😊

# N 입력
n = int(input())

# DP 테이블 0으로 초기화
dp = [0] * (n + 1)
dp[3] = 1
if n >= 5:
  dp[5] = 1
  for i in range(6, n + 1):
    # i-5킬로그램을 만들 수 있을 경우
    if dp[i - 5] != 0:
      dp[i] = dp[i - 5] + 1
    # i-3킬로그램을 만들 수 있을 경우
    elif dp[i - 3] != 0:
      dp[i] = dp[i - 3] + 1

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

시간복잡도는 O(N)입니다. 

 

 

 

백준 문제 풀이 깃허브 주소입니다 :)

https://github.com/Yiseull/baekjoon

GitHub - Yiseull/baekjoon