[백준/파이썬] 2839 설탕 배달 - 다이나믹 프로그래밍

➰ 2839번 설탕 배달

---

▪ 문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

▪ 입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

▪ 출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

 

 

💡 구현 아이디어

---

이 문제는 그리디로도 풀 수 있고, 다이나믹 프로그래밍 방법으로도 풀 수 있다. 문제를 보면 다이나믹 프로그래밍 문제로 잘 알려진 '1로 만들기'와 문제 형태가 매우 비슷하다. 그래서 어렵지 않게 이 문제가 DP 유형임을 파악했다. (하지만 이 문제는 그리디로 푸는 게 훨씬 간단하긴 하다... 저스트 DP 유형 연습을 위함...)

 

다이나믹 프로그래밍 소스코드를 작성하는 방법은 다음 2가지가 있다.

1) Top-Down, 하향식 방식

큰 문제를 해결하기 위해 작은 문제를 호출하는 방법으로 재귀 함수를 이용하여 코드를 작성한다.

2) Bottom-Up, 상향식 방식

작은 문제부터 차근차근 답을 도출하는 방법으로 반복으로 이용하여 코드를 작성한다. 상향식 방식에서 사용되는 결과 저장용 테이블은 'DP 테이블'이라고 부른다.

 

책 <이것이 취업을 위한 코딩 테스트다>를 보면 DP에서 가능하다면 재귀 함수를 이용하는 하향식 방식보다는 Bottom-Up 방식으로 구현하는 것을 권장한다고 나와있다. 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다. 따라서 이 문제를 Bottom-Up 방식으로 풀어보도록 하겠다.

 

이 문제의 DP 테이블에서 dp[n]의 값은 n에 대해 사용할 수 있는 봉지의 최소 개수이다. 따라서 DP 테이블은 모두 -1로 초기화한다. 단, N=3, 5일 때는 1로 초기화한다.

 

이제 문제에서 요구하는 내용을 점화식으로 표현해야 한다. 점화식이 보자마자 떠오르긴 어려울 것이다. 예제를 통해 직접 발견하면 된다.

 

N = 18인 예를 생각해보자. 

dp[18]는 3 + dp[15], 5 + dp[13] 두 가지로 쪼개는 것이 가능하다. 그리고 최소의 봉지 개수를 구하는 것이므로 둘 중 더 작은 값을 취하면 된다. 따라서 다음과 같은 점화식 표현이 가능하다.

dp[n] = 1 + min(dp[n - 3], dp[n - 5])

 

여기에 한 가지 더 생각해야 하는 것이 있다. N이 5보다 작은 수이면(당연히 3은 제외) 점화식을 해볼 것도 없이 나누어 떨어지지가 않기 때문에 dp[n] = -1의 결과가 나오게 된다. 따라서 더 조건을 추가해야 하는 것이 없는지 N이 더 작은 수일 때의 예를 생각해보자.

 

N = 6인 예를 생각해보자.

dp[6]은 3 + dp[3], 5 + dp[1] 두 가지로 쪼개는 것이 가능하다. 하지만 이때는 위의 예와는 달리 최솟값으로 구해버리면 아예 쪼갤 수 없는 dp[1]의 경우가 되므로 반대로 최댓값인 3 + dp[3]을 선택해야 한다. 이때의 점화식은 다음과 같이 표현할 수 있다.

dp[n] = 1 + max(dp[n - 3], dp[n - 5])

 

이를 소스코드로 구현하면 다음과 같다.

 

💻 소스 코드

---

x = int(input())
dp = [-1] * (x + 1)
 
dp[3] = 1
dp[5] = 1

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