[알고리즘][파이썬]2839-설탕 배달

문제

 

 

코드

import sys

N = int(sys.stdin.readline())

dp =[0,-1,-1,1,-1,1]+[0 for i in range(N)]

for i in range(6,N+1):
    dp[i] =-1
    if(dp[i-3]!=-1 and dp[i-5]!=-1):
        dp[i] = min(dp[i-3]+1,dp[i-5]+1)
    elif(dp[i-3]!=-1):
        dp[i] = dp[i-3]+1
    elif(dp[i-5]!=-1):
        dp[i] = dp[i-5]+1
    
print(dp[N])

 

 

 

코멘트

Dp를 이용해서 풀었다.

제시된 무게를 3킬로그램과 5킬로그램 봉지로 나눌 때 봉지 수가 최소가 되도록 하는 문제이다.

 

제시된 무게까지 for문을 돌려서 dp리스트에 최소 개수를 계속 저장할 수 있도록 했다. 그리고 인덱스 값이 커지면서 이전에 저장된 값을 활용할 수 있도록 코드를 작성했다.

 

for문을 돌 때 i-3, i-5 처리를 하기 때문에 인덱스 5까지의 무게는 리스트 선언할 때 미리 지정해 주었다💫