📖 BaekJoon No. 2839 - 설탕 배달

📌 문제

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

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

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

📌 입력 / 출력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

📌 예제

입력

18

출력

4

📌 해설 및 풀이

해당 문제를 처음 접근할 때는 그리디 알고리즘 방법으로 문제를 해결하려고 시도 했다.
그러나 해당 방법을 이용하려고 할 때, 5를 가장 먼저 나누고 그다음 나머지를 3으로 나누는 방식을 사용했을 때,
여러 테스트 케이스를 통과하지 못하는 상황이 발생하였다. (추후에 조사한 결과, 그리디 알고리즘 방식으로도 문제 해결이 가능하다.)
그래서 그리디 알고리즘 대신 다이나믹 프로그래밍 방식을 이용하여 문제를 해결하였다.

다이나믹 알고리즘 방식에서 상향식(Bottom-UP) 방법을 사용하였으며, 설탕이 0 킬로그램 일 경우부터 가정하여 문제에서 요구하는 나눗셈의 최대 방식인 설탕이 5 킬로그램일 때 까지 직접 가정하여 그 이후부터는 일정한 패턴을 이용한다.

0~5 킬로그램 까지의 경우를 생각해보자면 3,5 킬로그램을 제외한 나머지는 정확하게 N킬로그램을 만드는 것이 불가능하다. 그래서 3,5킬로그램은 정확히 한봉지씩 만들 수 있으므로 1씩 부여, 나머지는 해당 데이터를 통하여 최소한으로 만들어야하므로 압도적으로 큰 수를 부여한다. 해당 기초 작업이 다이나믹 프로그래밍 방식으로 문제를 해결하는 베이스가 된다.

그리고 6부터 다시 생각을 해보면, 3으로 나누면 2봉지가 되고, 5로 나누면 1이 남으므로 정확하게 N킬로그램을 만들 수 없다. 그러므로 6은 3으로 나눠 2봉지가 되어야 한다. 이것을 일정한 패턴으로 만든다면
min(sugar[6-3]+1,sugar[6-5]+1)으로 볼 수 있다. 작은 값을 찾게끔 만들면 된다. 해당 식을 풀이하면 sugar[3]은 앞서 초기 작업에서 1로 두었고, 해당 값에 1을 더한다. 6킬로그램을 3으로 나누는 것과 같은 행동이다. sugar[1]은 정확하게 나눌 수 없으므로 압도적으로 큰 수(무한대)로 배정되어있다. 무한대는 언제나 무한대로 표기되므로 가장 작은 값은 sugar[6-3]+1로 볼 수 있다.

요약하자면, 0~5킬로그램 까지는 직접 손으로 하드코딩을 하되, 6~N 킬로그램 까지는 패턴을 찾아 자동으로 연산이 가능하도록 프로그래밍 한다면 문제 해결이 가능하다.

📌 소스코드

N = int(input())
dn = [float("inf")]*5001
if len(dn) < 6:
    print(-1)
else:
    dn[3] = 1
    dn[5] = 1
    for i in range(6,N+1):
        dn[i] = min(dn[i-3]+1,dn[i-5]+1)
    if dn[N] == float("inf"):
        print(-1)
    else:
        print(dn[N])

📌 후기

타뷸레이션 방식(Bottom-UP)을 이용한 다이나믹 프로그래밍을 이론적으로 공부하고 이론을 직접 실전에 접목할 수 있는 난이도의 문제라고 생각한다. 해당 문제를 풀 때, 다이나믹 프로그래밍에 대해 가장 기초적인 피보나치 수열 정도만 구현 할 수 있었는데, 다양한 방식으로 접근 할 수 있었고, 다른 다이나믹 프로그래밍을 응용한 문제 또한 반복적인 패턴을 이용한 기초 작업이 필요하다는 것 또한 알게 되었다. 여러모로 다이나믹 프로그래밍에 대한 문제 접근 방식 또한 여러 방향으로 살펴 봐야함을 깨닫게 되는 문제였다.