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

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

2839번: 설탕 배달

dp로 문제를 풀어보았다.

 

dp[i]의 값은 N이 i일 때의 배달하는 봉지의 최소 개수이다. 만들 수 없다면 -1을 저장한다.

 

1. 먼저 길이가 N+1이고 모든 값이 -1인 리스트를 생성한다.

 

dp=[-1]*(n+1)

 

만약 N킬로그램을 만들 수 없는 경우 dp[i]의 값을 변경하지 않으면 된다.

 

2. dp[1]부터 dp[5]까지는 미리 값을 넣어준다.

dp[1:6]=[-1, -1, 1, -1, 1]​

 

 

3. 조건에 따라 dp[i]의 값을 결정한다. 

 

(1) dp[i-3]과 d[i-5] 모두 -1

 

N킬로그램을 만들 수 없으므로 dp[i]의 값도 -1이 된다.

 

(2) dp[i-3]만 -1

 

dp[i]의 값은 dp[i-5]+1이 된다.

 

(3) dp[i-5]만 -1

 

dp[i]의 값은 dp[i-3]+1이 된다.

 

(4) 둘 다 -1이 아님

 

dp[i]의 값은 dp[i-3]+1과 dp[i-5]+1 중 작은 값이 된다.

 

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

 

<전체 코드>

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