DP 문제를 마주했을 때 수의 패턴을 찾는 방식으로 점화식을 구하는 시도는 이 문제처럼 어려운 경우가 많습니다. 점화식을 세운다는 것은 다시 말해 이전 상태의 값들을 내가 전부 알고 있다고 했을 때 현재 상태의 값을 이전 상태의 값들로부터 구할 방법을 찾는 과정입니다.
f(x) = "설탕을 정확하게 x 킬로그램 배달하기 위해 배달해야 하는 봉지의 최소 갯수" (단, x 킬로그램의 배달이 불가능하다면 f(x) = -1)로 정의합시다.
이렇게 정의하면, 문제에서 입력 N이 주어졌을 때 f(N)을 출력하면 됨을 알 수 있습니다.
자, 어떤 x에 대해서 우리가 f(x)를 구하고자 한다고 합시다.
우리가 어떻게든 f(3), f(4), f(5), ..., f(x-1)을 전부 잘 구해뒀다고 믿고 이 값들을 이용해서 f(x)를 구할 방법이 있는지 찾는 것이 핵심입니다.
배달이 불가능한 경우는 일단 고려하지 않고 생각해봅시다.
설탕을 정확하게 x 킬로그램 배달하기 위해서는 둘 중 하나의 방법을 택해야 합니다. 일단 x-3 킬로그램을 배달한 다음 3 킬로그램 봉지를 하나 더 배달하거나, x-5 킬로그램을 배달한 다음 5 킬로그램 봉지를 하나 더 배달하는 것입니다. 봉지가 이 두 종류밖에 없으니 다른 방법은 없겠죠.
설탕을 정확하게 x 킬로그램 배달하기 위해 사용한 봉지의 갯수를 a개라 합시다. 일단은 최소 갯수를 생각하지 않고, 다양한 방법 중 한 가지를 택했다고 합시다. a는 f(x)보다 크거나 같을 것입니다.
비슷하게 x-3 킬로그램을 배달하기 위해 b개의 봉지를 사용하고, x-5 킬로그램을 배달하기 위해 c개의 봉지를 사용한다고 생각해봅시다.
아래 문장을 다시 들여다봅시다.
"설탕을 x 킬로그램 배달하기 위해서는 일단 x-3 킬로그램을 배달한 다음 3 킬로그램 봉지를 하나 더 배달하거나 x-5 킬로그램을 배달한 다음 5 킬로그램 봉지를 하나 더 배달해야 한다"
코드를 짜거나 수식을 세우거나 하기 전에 위 문장이 항상 옳은지, 아니라면 위 문장이 틀린 경우가 존재하는지 고민해봅시다. 항상 DP 문제를 풀 때에는 위 형태로 문장 형태의 명제를 만들 수 있어야 합니다. 이것이 체화가 되고 나면 자연스럽게 점화식을 바로바로 세울 수 있게 되는데, 그러한 점화식도 결국은 위의 문장 형태의 명제를 식으로 변환한 것에 불과합니다.
위 문장을 식으로 바꾸어봅시다. 아직은 점화식이 아닙니다.
a = b + 1 이거나 a = c + 1 입니다.
"설탕을 x 킬로그램 배달하기 위해서는 (a)
일단 x-3 킬로그램을 배달한 다음 (b)
3 킬로그램 봉지를 하나 더 배달하 (+1)
거나
x-5 킬로그램을 배달한 다음 (c)
5 킬로그램 봉지를 하나 더 배달해야 한다 (+1)"
문장이 식으로 바뀌는 과정이 보이나요? 이 과정이 자연스럽게 일어날 수 있어야 합니다.
이제 f(x)를 생각해봅시다.
a는 설탕을 x 킬로그램 배달하기 위해 사용한 봉지의 갯수라 했습니다. 여기에서는 "최소 갯수" 같은 표현이 없었죠. x 킬로그램 배달하는데, 설탕 봉지를 최소한으로 사용하려면 어떻게 해야 할까요?
x-3 킬로그램을 최소한의 설탕 봉지를 이용해서 배달한 다음 3 킬로그램 봉지를 하나 더 쓰거나, x-5 킬로그램을 최소한의 설탕 봉지를 이용해서 배달한 다음 5 킬로그램 봉지를 하나 더 써야 할 것입니다. 두 방법 중 설탕 봉지를 덜 쓰는 방법이 x 킬로그램을 배달하는데 설탕 봉지를 최소한으로 쓰는 방법이 되겠죠.
위에서 설명한 문장을 안 보고 본인이 다시 쓸 수 있나요? 메모장을 키거나 종이와 펜을 준비하고, 이 문장을 안 본 상태로 논리적으로 완벽하게 완성된 문장을 만들 수 있는지 테스트해보세요. 문장을 만들어본 다음, 다시 위 문장과 비교해봅시다.
위 문장을 만들 수 있으면, 이를 이제 점화식으로 옮길 수 있습니다.
f(x) = min(f(x-3) + 1, f(x-5) + 1)
"설탕을 x 킬로그램 배달하는데 필요한 최소 봉지의 갯수는 (f(x))
x-3 킬로그램을 배달하는데 필요한 최소 봉지의 갯수에 (f(x-3))
3 킬로그램 봉지를 배달하기 위해 필요한 봉지 하나를 더한 것과 (+1)
x-5 킬로그램을 배달하는데 필요한 최소 봉지의 갯수에 (f(x-5))
5 킬로그램 봉지를 배달하기 위해 필요한 봉지 하나를 더한 것 중 (+1)
더 작은 값이다 (min)"
이렇게 점화식을 세우는데 성공하면 이를 바탕으로 문제를 풀 수 있습니다. 점화식을 세우는 훈련이 잘 되면 문장을 만드는 과정을 생략하고 바로 f(x)를 정의하고 식을 세우는 방향으로 갈 수 있지만 그 전까지는 이런 식으로 f(x)를 문장 형태로 정확하게 정의하고 f(x)를 이전 상태로부터 구해내는 방법 또한 문장 형태로 정확하게 서술하는 훈련이 필요합니다.
잊기 쉽지만 정말 중요한 부분인데, 모든 f(x)의 값을 온전하게 구하기 위해서는 초기 항들이 잘 주어져야 합니다. 이 경우에는 f(0) = 0, x가 음수이거나 1 이거나 2인 경우 f(x) = -1이라는 정보만 있으면 충분합니다.
마지막으로, 이 점화식을 정말 정확하게 서술하기 위해서는 배달이 불가능한 경우들도 잘 고려해줘야 합니다. 위에서는 배달이 불가능한 경우는 고려하지 않고 점화식을 세웠죠. x <= 2일 때의 f(x) 값은 모두 올바르게 정의해주었습니다. x >= 3일 때, f(x)가 -1일 조건은 정확히 어떻게 될까요?
배달이 불가능한 경우를 점화식에 포함하여 최종 점화식을 완성하는 것은 숙제로 남겨두겠습니다.

1exxn 1년 전
3부터 22까지의 최적의 모든 경우의 수를 봤는데
아직도 찾지 못했습니다
힌트라도 주시면 감사하겟습니다
3 - 3
4 - X
5 - 5
6 - 3 3
7 - X
8 - 3 5
9 - 3 3 3
10 - 5 5
11 - 3 3 5
12 - 3 3 3 3
13 - 3 5 5
14 - 3 3 3 5
15 - 5 5 5
16 - 3 3 5 5
17 - 3 3 3 3 5
18 - 3 5 5 5
19 - 3 3 3 5 5
20 - 5 5 5 5
21 - 3 3 5 5 5
22 - 3 3 3 3 5 5
23 - 3 5 5 5 5
1
0
1
2
0
2
3
2
3
4
3
4
3
4
5
4
5
4
5
6
5
지금까지 찾은 건데 3으로 딱딱 나누면 뭐가 있는거?는 발견했습니다.