DP - 선택 순서 관찰

가끔 PS에서 $n$개 중 몇 개를 골라 특정 값을 최대 혹은 최소화하는 문제가 나타난다.

대표적으로 냅색 문제가 있는데, 보통 냅색을 풀 때 "$1$ ~ $i$번 물건을 고려한 최대/최솟값"과 같이 DP식을 정의한다.

즉 각각의 물건은 $1$번부터 $n$번까지 "순서"를 매길 수 있고, 어떤 순서로 정하든 최종적인 답에는 영향을 주지 않는다.

직관적으로는 당연할 수 있지만 이게 왜 가능한지 생각해 보자. 먼저 임의의 순서대로 물건에 $1$ ~ $n$번까지 번호를 매겼다고 가정하자.

이제 냅색의 솔루션이 되는 임의의 선택 순서 $a_1, a_2, ..., a_m$을 생각하자($a_i$는 물건의 번호이다).

만약 $a_i > a_{i+1}$인 $i$가 존재한다면, $a_i$와 $a_{i+1}$을 바꾼 순서 $a_1, ..., a_{i+1}, a_i, ..., a_m$ 또한 냅색의 솔루션이 됨은 자명하다.

따라서 모든 솔루션을 오름차순으로 표현할 수 있기 때문에 인덱스를 어떤 순서로 정하든 상관이 없는 것이다.

냅색은 집합을 고르는 문제이기 때문에 선택 순서에 특별한 제약이 없지만, 아래 문제들은 제약이 존재하며 그에 따라 인덱스 정렬 기준이 달라진다.

E. Fire (Codeforces Round #436)

http://codeforces.com/contest/864/problem/E

$n$개의 물건이 있고 각각 타버리는 시간 $d_i$, 구하는 시간 $t_i$, 가치 $p_i$가 있을 때, 가치의 합이 최대가 되도록 물건들을 구하는 문제다.

직관적으로 생각해 보면 타버리는 시간이 짧을수록 먼저 구하는 것이 이득일 것 같지만, 그렇다고 그리디하게 무조건 짧은 것을 선택하면 안 된다.

대신 타버리는 시간이 짧은 순으로 번호를 매겨 DP를 돌리는 방법으로 접근할 수 있다. 즉, $d_i \leq d_{i+1}$을 만족하도록 인덱스를 부여하는 것이다.

이제 임의의 솔루션 순서 $a_1, a_2, ..., a_m$가 인덱스의 오름차순으로 표현 가능함을 보일 것이다.

$s_i=\sum_{k=1}^{i}t_{a_i}$ 라고 하면, 솔루션은 문제의 조건에 따라 아래 식을 만족해야 한다.

$s_i \leq d_{a_i} (1 \leq i \leq m) ... (1)$

$a_i > a_{i+1}$인 $i$가 존재한다고 가정하자. 먼저 인덱스 조건과 (1)에 의해 다음의 식이 성립한다.

$d_{a_{i+1}} \leq d_{a_i} ... (2)$

$s_i = s_{i-1}+t_{a_i} \leq d_{a_i} ... (3)$

$s_{i+1} = s_{i-1}+t_{a_i}+t_{a_{i+1}} \leq d_{a_{i+1}} ... (4)$

(2)와 (4), $d_{a_i} \geq 0$ 에 의하여

$s_{i-1}+t_{a_{i+1}} \leq s_{i-1}+t_{a_i}+t_{a_{i+1}} \leq d_{a_{i+1}} \leq d_{a_i}$

$s_{i-1}+t_{a_{i+1}} \leq d_{a_{i+1}} ... (5)$

$s_{i-1}+t_{a_{i+1}}+t_{a_i} \leq d_{a_i} ... (6)$

(5), (6)번 식을 보면 알겠지만, (3), (4)번 식에서 $a_i$ 대신 $a_{i+1}$을, $a_{i+1}$ 대신 $a_{i}$을 대입한 것과 일치한다.

다시 말해, $a_i$와 $a_{i+1}$을 바꾼 순서 $a_1, ..., a_{i+1}, a_i, ..., a_m$ 또한 솔루션이 된다.

이제 안심하고 $d_i$순으로 정렬하여 dp를 돌릴 수 있다. $dp[인덱스][합]$의 점화식을 구해서 풀자.

생존자 (Google Code Jam Korea 2012 본선 라운드 A)

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

위 문제와 상당히 비슷하게 생겼다. $p_i + s_i$순으로 정렬해보자. 즉, $p_i + s_i<=p_{i+1} + s_{i+1}$을 만족하도록 인덱스를 부여하는 것이다.

마찬가지로 임의의 솔루션 순서 $a_1, a_2, ..., a_m$가 인덱스의 오름차순으로 표현될 수 있다는 것을 보일 것이다. 증명은 위 문제와 똑같다.

$b_i=\sum_{k=1}^{i}s_{a_i}$ 라고 하면, 솔루션은 다음의 식을 만족해야 한다.

$b_i \leq p_{a_{i+1}} (1 \leq i < m) ... (1)$

$a_i > a_{i+1}$인 $i$가 존재한다고 가정하자. 인덱스 조건과 (1)에 의해

$p_{a_{i+1}} + s_{a_{i+1}} \leq p_{a_i} + s_{a_i} ... (2)$

$b_i = b_{i-1} + s_{a_i} \leq p_{a_{i+1}} ... (3)$

$b_{i+1} = b_{i-1} + s_{a_i} + s_{a_{i+1}} \leq p_{a_{i+2}} ... (4)$

(2)와 (3)에 의하여

$b_{i-1} + s_{a_i} + s_{a_{i+1}} \leq p_{a_{i+1}} + s_{a_{i+1}} \leq p_{a_i} + s_{a_i}$

$b_{i-1} + s_{a_{i+1}} \leq p_{a_i} ... (5)$

(5)번 식은 (3)번 식의 $a_i$ 대신 $a_{i+1}$, $a_{i+1}$ 대신 $a_i$를 대입한 것과 동일하며, (4)번 식은 $a_i$와 $a_{i+1}$을 바꾸어도 자명하게 성립한다.

따라서 $a_i$와 $a_{i+1}$을 바꾼 순서 $a_1, ..., a_{i+1}, a_i, ..., a_m$ 또한 솔루션이 된다.

이제 $p_i+s_i$ 순으로 정렬하고, $dp[인덱스][위치]$ 와 같이 특정 위치에 도달 가능한지 판단하는 식으로 문제를 해결할 수 있다.

사전에 정렬하여 dp를 돌리는 문제는 상당히 많다. 물론 냅색처럼 집합을 선택하거나 선택 순서에 특별한 제약이 없는 경우가 대부분이긴 하지만.

관련 문제

색종이 올려놓기 (KOI 1999 초등 3)

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

Babaei and Birthday Cake (CF Round #343 D)

http://codeforces.com/contest/629/problem/D