설탕배달, DP 기본 지식 1일차

DP 문제임을 알고 풀며, DP 문제 풀이 방식에 익숙해지기 위해 해당 글을 씁니다.

 해당 문제는 수학적으로도 해결이 가능하기도 합니다. 다만 완전 탐색(브루토포스)으로 해결이 가능하다는 점을 눈 여겨 봐야 합니다.

주먹구구식 방식으로 해결이 가능하다는 점과 문제를 재귀로 해결이 가능하다는 점을 보았을 때 중첩된 하위 구조의 특징을 가지고 있다는 점을 알 수 있고, 이를 통해 DP로 해결이 가능하다는 점을 알 수 있습니다.

중첩된 하위 구조를 가지고 있다는 것을 어떻게 알 수 있을까요? 재귀를 타고 내려감에 따라 호출된 똑같은 값이 있다면 이전에 계산된 값을 쓰면 되기에 최적화가 가능합니다.

 DP의 첫번째글이니까 더 적어 보려 합니다. 이름이 왜 DP일까요?, 흔히 말하는 DP 테이블, 메모제이션이 있다고 해서 DP 문제일까요? 아닐까요? 아닙니다. 정답을 찾아가는 도중에 상태를 보고 선택을 하기 때문에 동적 프로그래밍이라고 이름을 지엇다고 생각합니다.

잡설은 그만하고, 설탕 문제를 한번 볼까요?

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

눈여겨볼만한 점은 다음과 같습니다.

1. 정확한 N 킬로그램을 배달한다.
2. 최대한 적은 봉지를 들고 간다.
3. 설탕 공장에서 만드는 설탕은 3kg, 5kg 봉지

여기서 선택할 수 있는 요소는 무엇일까요? 바로 3kg, 5kg 봉지입니다. 그렇다면 상태는 무엇일까요? 현재 선택한 설탕의 무게임을 유추해볼 수 있습니다. ? 를 띄울 수 있지만 문제 내용도 없고, 선택할 요소도, 상태가 될 만한 요소도 거의 없다는 점을 생각한다면 소거법에 의해서도 무게임을 추측해볼 수 있습니다.

상태 -> 무게 w
선택 -> 3kg, 5kg

이제 이를 완전 탐색으로 내려 가봅시다.

루트 노드는 설탕의 무게를 0을 나타내고 있고, 왼쪽/오른쪽 자식은 선택에 따라 내려감을 나타냅니다.
색을 칠한 요소는 중복된 요소를 나타냅니다.

 그렇기 때문에 중복된 요소를 계산을 굳이 또 할 필요도 없기도 하고, 현 문제는 간단한 문제이지만 복잡한 문제인 경우 하나의 연산이 무거워질 수록 중복된 연산은 이미 계산된 내용을 기반으로 재활용한다면 최적화가 이루어집니다.

그리고 이렇게 중복된 하위 문제가 나오는 것을 중첩 하위 구조임을 알 수 있습니다.

dfs 문제에서 보던 그림과 비슷하기도 합니다. 이를 가지고 메모이제이션을 해봅시다.

문제에서 상태는 1개임으로 1차원 테이블 하나 생성하면 충분할 듯합니다.

나타내보면 위 그림과 같습니다.

글을 적다보니 이런 생각도 듭니다. 9가 3과 5로 이루워진 조합은 3 + 3 + 3이고, 10은 5 + 5, 15는 5 + 5 + 5, 3 + 3 + 3 + 3 + 3 + ... 어떻게 15일 때 어떻게 5 + 5 + 5임을 보장할까? 란 그런 생각도 들 것 같습니다.

그런 걱정은 잠시 넣어두어도 될 듯합니다.

매번 최적임을 보장하고 있기 때문에 15는 무조건 5,5,5를 선택하게 됩니다.

예제 문제의 18은요? 5 + 5 + 5 + 3 입니다.

그렇다면 각 무게에서 최적의 봉지 선택은 어떻게 할까요?

저는 0부터 18까지 순방향으로 진행하면서 현재 무게에서 - 3, - 5를 통해 이미 저장된 값을 확인했습니다.
즉, 15는 DP[15-3], DP[15-5] 의 값을 비교해서 최소 값을 선택해 봉지 하나(3을 선택하든 5을 선택하든 봉지는 하나 추가됨)를 추가해서 저장합니다. 즉 DP[12] -> 4, DP[10] -> 2 => 2 + 1 즉 3입니다. (위 테이블은 잘못 그렸네요. 사소하니 넘어..가요)

여튼.. 이렇게 구한 MIN(DP[I-3], DP[I-5])+1은 점화식이니 뭐라니 등.. 제일 기초적인 문제를 통해 DP를 엿보았습니다.

다음은 2차원 문제로 와보면 좋겠네요. DP 뿌셔요.