[BOJ] 백준 2839 설탕 배달 (Swift)

문제

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

2839번: 설탕 배달

풀이

이 문제는 어떤 알고리즘을 사용하여 풀 수 있을까요?
봉지가 3, 5의 단위로만 존재하고 5가 3의 배수가 아니기 때문에, 그리디 알고리즘으로는 풀 수 없습니다.

그래서 다이나믹 프로그래밍 기법을 떠올릴 수 있습니다.

다이나믹 프로그래밍은 점화식만 세우면 쉽게 풀 수 있습니다.

DP 테이블을 어떤식으로 채울 수 있을까요?

봉지가 3, 5의 단위로만 존재하기 때문에, 1, 2, 4 의 설탕은 들고갈 수 없고, 3과 5는 1로 채워지겠네요.

먼저, 초기값은 3킬로그램 일 때 1, 5킬로그램일 때, 1이 될 것입니다.
가장 먼저 6킬로그램일 때를 살펴보죠.

6킬로그램은 3킬로그램 2개를 사용해서 만들 수 있습니다.
5킬로그램이랑 1킬로그램 봉지를 사용해서도 만들 수 있겠죠? 하지만 1킬로그램 봉지가 없으므로 만들 수 없습니다.

따라서 6킬로그램은 3킬로그램 봉지 2개를 사용해서 만드는 것이 봉지의 최소로 사용하는 경우겠네요.

7킬로그램은 만들 수 있는 경우가 없습니다.
3 + 4, 5 + 2 .. 4킬로그램, 2킬로그램 봉지가 없기 때문이죠.

8킬로그램은 어떨까요?
3 + 5로 봉지 2개로 가져갈 수 있겠군요.

규칙이 보이시나요??

(현재 - 3)킬로그램, (현재 - 5)킬로그램 에서 최소 값 중 하나의 봉지를 더 사용하는 게 최소 봉지가 됩니다.

점화식은 어떻게 될까요?

초기 값
$f(3) = 1, f(5) = 1$
점화식
$if\ x > 3, f(x) = min(f(x - 3), f(x - 5)) + 1$

이제 이것을 소스코드로 옮기기만 하면 됩니다.

소스코드

후기

다이나믹 프로그래밍을 떠올렸다면 점화식을 쉽게 구할 수 있기 때문에 쉽게 풀 수 있는 문제였습니다.