BOJ 2419. 사수아탕
문제 해석
수직선 위 \(N\)개의 점에 바구니가 하나씩 있고 모든 바구니에는 사탕이 \(M\)개씩 들어있다. 나는 처음에 원점에 있고 수직선 위에서 \(1\)의 속력으로 이동할 수 있으며, 현 위치에 바구니가 있다면 안에 든 사탕을 시간 소모 없이 전부 먹을 수 있다. 모든 바구니에서 \(1\)초마다 사탕이 \(1\)개씩 줄어든다고 할 때, 사탕을 최대 몇 개나 먹을 수 있는가?
접근
대충 봐도 BOJ 2315. 가로등 끄기, BOJ 4243. 보안 업체 와 결이 같아 보이며, 실제로 DP가 돌아가는 모양새 자체는 거의 똑같다. 하지만 이 문제의 차별점은 DP가 겉으로 드러나 있지 않고 끄집어내야 한다는 것인데, 이 글에서는 여기에 초점을 두겠다. 저 두 문제는 먼저 풀어보기를 추천한다.
원점에 바구니를 하나 추가한 다음 바구니들의 위치를 정렬하자. 원점에 이미 바구니가 있어서 \(0\)이 \(2\)개가 되어도 둘은 인접할 것이고 거리가 \(0\)이라 이동해도 시간이 흐르지 않아 답은 동일하게 나올 것이다. 이제 두 가지 관찰을 한다.
- 사탕을 안 먹고 바구니를 그냥 지나치거나, 바구니와 바구니 사이에서 방향을 바꾸면 결코 이득이 없으니 그러지 않는다.
- 출발할 때부터 귀납적으로 생각하면 잡은 바구니의 집합은 언제나 하나의 연속 구간 \([l, r] (0 \le l \le r \le N)\)이다. 최근에 잡은 바구니(그래서 지금 와 있는 바구니)는 \(l\)이나 \(r\)이고, 다음으로 잡으러 갈 바구니는 \(l-1\)이나 \(r+1\)이다.
위의 두 문제는 이것을 그대로 코드로 가져가면 풀리는데 이 문제는 아니다. 문제에 제공된 예시에서 \(x=4\)에 바구니를 추가해 보자. \([0, -3, 1, 4]\) 경로로 움직일 때와 \([0, 1, -3, 4]\) 경로로 움직일 때 걸리는 시간이 다르기 때문에 마지막 바구니인 \(6\)에 남아 있는 사탕 수가 달라진다. 즉 이대로는 부분문제 구조가 성립하지 않으며, DP table에 시간 차원을 붙여야 하지만 그랬다간 MLE가 날 것이다.
한 발 물러나 우리의 최대화 목적함수를 식으로 써 보자. \(i\)번째 바구니(\(x_i\)에 있는 바구니가 아니라 \(i\)번째로 잡은 바구니)를 잡는 시각을 \(t_i\)라고 하면 우리의 목적함수는 아래와 같다.
\[F = \sum_{i=0}^N \max(0, M - t_i)\]저 \(\max\)가 없었으면 좋겠다. \(t_i\)는 \(0\)에서부터 단조증가하니까 \(\max(0, M - t_i)\)는 처음에는 \(+\)이다가 어느 순간부터 계속 \(0\)일 텐데, 그 순간을 변수로 도입하는 것이 아이디어다. 최적해에서 \(t_i \lt M\)인 마지막 \(i\)를 \(K\)라고 하고 식을 다시 쓰자.
\[F = \sum_{i=0}^K (M - t_i) = KM - \sum_{i=0}^K t_i\]BOJ 4243 을 풀었다면 \(\sum_{i=0}^K t_i\)를 최소화하는 방법은 알고 있을 것이다. \(K\)를 안다면 말이다. 그런데 \(K\)를 모르니까, 전부 해보면 된다. 즉 \(k\) 값을 바꿔 보면서 \(\mathcal{O}(N^2)\)짜리 DP를 \(\mathcal{O}(N)\)번 돌리면 되므로, 전체 \(\mathcal{O}(N^3)\) 시간에 풀린다.
\[F = \max_{k=0}^N F_k = \max_{k=0}^N \left[ kM - \sum_{i=0}^k t_i \right]\]