Yukicoder No. 54 Happy Hallowe'en

Yukicoder No. 54 Happy Hallowe'en

문제 링크

 

문제

오늘 할로윈을 맞아 타로군은 이웃에 사탕을 받으러 가기로 했습니다.

 

이웃에는, 타로군의 집 이외에 $N$ 채의 집이 있습니다.

$i$번째 집에 가면 사탕을 $V_i$ 개 받을 수 있습니다.

이웃 친구와 공평하게 사탕을 나눠 가지기 위해서

이미 사탕을 $T_i$ 개 이상 가지고 있으면, (해당 집에서는) 사탕을 하나도 받을 수 없습니다.

 

타로군이 처음에 사탕을 하나도 가지고 있지 않고, 주위 집을 원하는 순서로 방문할 수 있을 때,

타로군이 받을 수 있는 사탕의 최댓값을 구해주세요.

같은 집은 $1$번 밖에 방문할 수 없습니다.

 

입력

$1$번째 줄에, 이웃의 집의 수 $N \ (1 \le N \le 10000)$이 주어집니다.

다음 $N$ 개의 줄의 $i$번째 집 $(1 \le i \le N)$에서 받을 수 있는 사탕 수를 의미하는 정수 $V_i \ (1 \le V_i \le 10000)$과, 사탕을 받을 수 있는 제한을 나타내는 정수 $T_i \ (1 \le T_i \le 10000)$이 공백으로 구분되어 주어집니다.

출력

타로군이 받을 수 있는 사탕 개수의 최댓값을 출력해주세요.

마지막에 개행문자를 넣어주세요.

예제 설명

1. $1$번째 집에 가면, 가지고 있는 사탕이 $0$개이므로, $1$개 받을 수 있습니다. 그 후, $2$번째 집에 가면, 가지고 있는 사탕이 $1$개 이므로 $3$개 더 받을 수 있지만, 그보다 $3$번째 집에 가서 $5$개를 받는 것으로 최대 $1+5=6$개 사탕을 받을 수 있습니다.
2. 모든 집을 적절한 순서로 방문하면 최대 $5$개의 사탕을 받을 수 있습니다.
3. $1, 2, 6, 7$번째 집에 순서대로 방문하면, 사탕을 $2, 2, 3, 4$개 받을 수 있습니다.
4. sugim님이 제공해주신 예제입니다.

풀이

힌트

집을 방문하는 순서가 정해져 있으면, 쉽게 동적 계획법으로 풀 수 있습니다. 집을 어떤 순서로 방문하는게 좋을까요?

풀이

집을 $s_1, s_2, s_3, \cdots, s_K$ 순서로 방문한다고 합시다. 우리는 인접해서 방문하는 두 집인, $a = s_i$ 번째와 $b = s_{i+1}$ 번째 집에 집중할 것입니다.

 

$s_{i-1}$ 번째 집까지 방문했을 때 얻은 총 사탕의 개수를 $X$ 개라고 합시다.

그러면, $a$와 $b$ 순서대로 집을 방문할 때 조건은 $a$번째 집을 방문하기 전의 조건인 $X < T_a$와 $b$번째 집을 방문하기 전의 조건인 $X+V_a < T_b$가 있습니다. 즉, $X < \min(T_a, T_b-V_a)$를 만족해야 합니다.

 

만약에 두 집의 순서를 바꿔서 $s_1, s_2, \cdots, s_{i-1}, b, a, s_{i+2}, \cdots, s_K$순으로 방문한다면, 만족해야 하는 조건은 $X < \min(T_b, T_a-V_b)$가 될 것입니다.

두 방법이 얻을 수 있는 사탕의 개수는 동일합니다. 그리고 차이가 있는 조건은 $X$가 $\min(T_a, T_b-V_a)$ 보다 작은지 $\min(T_b, T_a-V_b)$ 보다 작은지의 차이가 있습니다.

그래서 우리는 "올바른 순서를 유지하면서, $a$와 $b$의 순서를 바꿀 수 있는지"에 대해 집중해 보겠습니다.

더 $X$의 범위가 넓은 경우, 즉 $\min(T_a, T_b-V_a) \le \min(T_b, T_a-V_b)$인 경우 $a$와 $b$의 순서를 바꾼 것도 답이 될 수 있습니다.

 

$\min(T_a, T_b-V_a) = T_a$이라면 조건에 의해서 $T_a \le T_a - V_b$를 만족해야하므로, 모순입니다.

즉, $\min(T_b-V_a, T_a) = T_b-V_a$ 이고, 대소관계에 따라 식을 정리하면 $T_b-V_a \le T_a-V_b$가 되며, 식을 조금 바꾸면 $T_b+V_b \le T_a+V_a$가 됩니다.

이는 방문하는 순서로 $T_i + V_i$가 큰 것이 먼저 올 경우, 방문하는 순서가 인접한 두 집을 바꿀 수 있다는 의미가 됩니다.

 

즉, 우리가 고려해야 하는 답은 $T_i + V_i$ 순으로 정렬된 답만 고려하면 됩니다. 그렇지 않은 답이 존재할 경우, $T_i + V_i$순으로 오름차순 정렬된 답으로 바꿀 수 있기 때문입니다.

 

나머지로 사탕 개수를 얼마나 가질 수 있는지는 동적 계획법을 통해서, 가령이면 $DP_{i, j}$를 $i$번째 집까지 방문했을 때, $j$ 개의 사탕을 가질 수 있는지 등으로 해결할 수 있습니다.

 

시간 복잡도는 $V$와 $T$의 최댓값을 $MAX$라고 했을 때 $O(N \log N + N \times MAX)$ 입니다.

 

코드: https://yukicoder.me/submissions/733913