[백준/Python] 2839 설탕 배달

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

 

 

사용 알고리즘: DP

 

 

상근이가 설탕을 정확하게 N kg 배달해야 한다. 이 때 설탕은 3kg, 5kg 두 가지 봉지에 담겨져 있다. 상근이가 설탕을 정확하게 N kg 배달해야할 때 최소 봉지의 개수를 구하는 프로그램 구현

 

입력

N (3 <= N <= 5000)

 

출력

상근이가 배달하는 봉지의 최소 개수 출력, 만약 정확하게 N kg 을 맞출 수 없다면 -1 출력

 

 

- 인덱스 1부터 사용할 것이기 때문에 dp 배열의 길이를 (n+1) 로 만들고, 기본 값을 -1 로 초기화

- n 의 값이 5 이상인 경우와 아닌 경우를 나누어 초기화 시킴 (n 이 3, 4 인 경우 dp[5] 를 먼저 초기화 시키면 인덱스 에러남)

# 입력받기
n = int(input())

# dp 초기화
dp = [-1] * (n+1)

if n >= 5:
    dp[5] = 1
dp[3] = 1

 

 

dp 로 풀려고 하니 별다른 방법이 보이지 않아 숫자를 써놓고 값을 써가며 규칙을 찾았다. 

 

구현 로직

• 5의 배수인 경우 -> dp[i] = dp[i-5] + 1
• 3의 배수인 경우 -> dp[i] = dp[i-3] + 1
• 위의 경우를 통과하지 못한 경우 dp[n-5] 와 dp[n-3] 값 중 더 작은 값에 +1 을 더한 값 (dp[i-5] > 0 and dp[i-3] > 0 여야 함)
• 위의 세가지 경우를 모두 통과하지 못한 경우 처음 초기화 시킨 -1 값이 dp[i] 의 값이 됨

 

전체 코드

n = int(input())

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

if len(dp) >= 6:
    dp[5] = 1
dp[3] = 1

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