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

2023년 9월 19일

문제 링크 : 2839번 - 설탕 배달

문제

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

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

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

입력

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

출력

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

알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 그리디 알고리즘

---

문제 접근

수학적으로 계산해도 될 것 같지만, 나는 DP를 활용할 수 있을 것 같아 DP로 접근해 보았다.
접근 방법은 이러하다.

1. N 킬로그램의 설탕을 배달하려고 할 때, 최소한의 봉지만을 들고 가고싶다.
   
   
2. 그렇다면 우리는 Bottom-Up 방식으로, 0 킬로그램부터 3 / 5 킬로그램 봉지를 이용해 최소한의 봉지 개수만의 조합을 꾸려볼 것이다.
   
   
3. 3 / 5 킬로그램 봉지의 조합으로 만들 수 없는 킬로그램이라면 -1을, 최소한의 개수로 조합할 수 있는 킬로그램이라면 해당 조합 정보를 List에 저장한다.
   
   
4. 만약 10 킬로그램의 설탕을 예시로 들어보자. 그럼 다음과 같은 두 경우를 고려해 볼 수 있을 것이다.
   - 10 킬로그램에서 3 킬로그램 봉지 한 개를 무조건 담는다고 가정. 그렇다면 Bottom-Up 방식으로 접근했으니 10 - 3 = 7 킬로그램의 설탕에 대한 최소 조합 정보가 List에 담겨있을 것이다.
   - 10 킬로그램에서 5 킬로그램 봉지 한 개를 무조건 담는다고 가정. 그렇다면 Bottom-Up 방식으로 접근했으니 10 - 5 = 5 킬로그램의 설탕에 대한 최소 조합 정보가 List에 담겨있을 것이다.
   
   
5. 두 가지 경우에서, 7 킬로그램은 조합이 불가능하기에 -1이 담겨있으므로 3 킬로그램 봉지 한 개를 무조건 담는 경우는 불가능한 경우이므로 무시하고, 5 킬로그램은 3 / 5 킬로그램 봉지가 각각 0 / 1 개 필요하므로 가능한 조합이다.
6. 그렇다면 10 킬로그램의 설탕을 최소한의 봉지 개수로 조합하는 경우는 10 - 5 킬로그램의 봉지 조합 + 5 킬로그램 봉지 1개이다. ( 0 / 2 개 )

이 과정에서 볼 수 있듯, DP로 접근한다면 다음과 같은 점화식을 도출할 수 있다.

만약 DP[n - 3]이 -1 (조합 불가능) 이라면 DP[n] = DP[n - 5] + 1

만약 DP[n - 5]이 -1 (조합 불가능) 이라면 DP[n] = DP[n - 3] + 1

만약 DP[n - 3], DP[n - 5]이 모두 -1 이라면, DP[n] = -1

DP[n - 3], DP[n - 5]이 모두 -1이 아니라면,
	DP[n] = min(DP[n - 3] + 1 , DP[n - 5] + 1)

 

---

순서도

1. 3 킬로그램, 5 킬로그램 봉지 개수를 한 쌍으로 저장하는 dp를 List로 선언한다.

2. 기저 조건인, 0 킬로그램 ~ 5 킬로그램 까지의 조합은 특수케이스로 지정한다.

3. 점화식에 근거해 Bottom-Up 방식으로 입력값으로 주어진 N 킬로그램까지 dp를 채워나간다.

4. N 킬로그램일 때의 3 / 5 킬로그램 봉지 개수의 각 합을 출력한다.

 

---

입력 예제

11

 
0 ~ 5 킬로그램 까지의 기저 조건을 dp에 저장한다.
dp = [ [ -1,  -1 ] , [ -1,  -1 ] , [ 1 ,  0 ] , [ -1,  -1 ] , [ 0 , 1 ] ] 
6 킬로그램의 경우부터 dp를 채워나가 본다.
 
6 킬로그램 = dp[ 1 ]이 -1 이므로 dp[ 3 ]의 조합에서 3 킬로그램 봉지 한 개를 추가한 [ 2, 0 ]을 저장
7 킬로그램 = dp[ 2 ], dp[ 4 ] 모두 -1 이므로 [ -1, -1 ]을 저장
8 킬로그램 = dp[ 3 ] = [ 1, 0 ], dp[ 5 ] = [ 0, 1 ] 이므로 각각 3 / 5 킬로그램 봉지를 한 개 더해도 같음. [1 , 1]을 저장
9 킬로그램 = dp[ 4 ]는 -1 이므로 dp[ 6 ]의 조합에서 3 킬로그램 봉지 한 개를 추가한 [ 3, 0 ]을 저장
10 킬로그램 = dp[ 7 ]은 -1 이므로 dp[ 5 ]의 조합에서 5 킬로그램 봉지 한 개를 추가한 [ 0, 2 ]를 저장
11 킬로그램 = dp[ 8 ] = [ 1, 1 ] , dp[ 6 ] = [ 2 , 0 ] 이므로 각각 3 / 5 킬로그램 봉지를 한 개 더해도 같음. [ 2, 1 ]을 저장
 
따라서, 11 킬로그램의 설탕에 대한 최소 봉지 개수는 3이다.
 

출력 예제

3

---

주의할 점

 

---

전체 코드

# 2839

N = int(input())

dp = [
    [-1, -1],
    [-1, -1],
    [-1, -1]
]

cnt = 3

while(cnt <= N):
    if cnt == 3:
        dp.append([1, 0])
    
    elif cnt == 4:
        dp.append([-1, -1])

    elif cnt == 5:
        dp.append([0, 1])

    else:
        if dp[cnt - 3][0] == -1 and dp[cnt - 5][0] == -1:
            dp.append([-1, -1])

        elif dp[cnt - 3][0] == -1 and dp[cnt - 5][0] != -1:
            dp.append([dp[cnt - 5][0], dp[cnt - 5][1] + 1])

        elif dp[cnt - 3][0] != -1 and dp[cnt - 5][0] == -1:
            dp.append([dp[cnt - 3][0] + 1, dp[cnt - 3][1]])
        else:
            if (dp[cnt - 3][0] + 1 + dp[cnt - 3][1]) < (dp[cnt - 5][0] + dp[cnt - 5][1] + 1):
                dp.append([dp[cnt - 3][0] + 1, dp[cnt - 3][1]])
            else:
                dp.append([dp[cnt - 5][0], dp[cnt - 5][1] + 1])
    cnt += 1

if dp[-1][0] + dp[-1][1] < 0:
    print(-1)
else:
    print(dp[-1][0] + dp[-1][1])

 

---

풀이 후기

다이나믹 프로그래밍을 이 문제에 어떻게 접목시킬 것인가? 에 대한 고민이, 설계하고 코드로 옮기는 시간보다 더 많이 걸리는 것이 DP 문제의 핵심이라고 생각한다.
DP문제는 많이 풀어보는게 확실히 도움이 많이 된다.