재의 마녀의 여행

$i$번 나라에 도착했을 때 가지고 있는 금화를 $X$라고 하자.

$i$번 나라를 방문하려면 $X \geq A_i+B_i$여야 하며, 방문한 뒤 가지고 있는 금화는 방문 전의 금액과 관계없이 정확히 $B_i$가 된다.

따라서 지금까지 방문한 나라의 구체적인 목록은 중요하지 않다. 현재 가지고 있는 금화가 같다면, 그중 방문한 나라의 수가 가장 많은 상태만 남기면 된다.

DP 정의

앞에서부터 나라를 처리하면서, 다음 값을 관리한다.

$$D(x)=\text{현재 금화가 }x\text{개인 상태에서 방문한 나라 수의 최댓값}$$

처음에는 아무 나라도 방문하지 않았으므로 다음과 같이 초기화한다.

$$D(C)=0$$

도달할 수 없는 상태의 값은 $-\infty$로 둔다.

$i$번 나라를 방문할 수 있는 이전 상태에서는 현재 금화가 $A_i+B_i$ 이상이어야 한다. 따라서

$$M=\max_{x\geq A_i+B_i}D(x)$$

를 구한다.

$M$이 $-\infty$가 아니라면, 해당 상태에서 $i$번 나라를 방문할 수 있다. 방문 후 금화는 $B_i$개가 되므로 다음과 같이 갱신한다.

$$D(B_i)\leftarrow\max(D(B_i),M+1)$$

$i$번 나라를 방문하지 않는 경우에는 기존 상태가 그대로 유지되므로 별도의 갱신이 필요하지 않다.

관리해야 하는 금화의 종류

처음에는 금화가 $C$개이고, 나라를 한 번 이상 방문했다면 현재 금화는 마지막으로 방문한 나라의 $B_i$와 같다. 따라서 등장할 수 있는 금화의 값은

$$C,B_1,B_2,\cdots,B_N$$

뿐이다.

이 값들을 정렬한 뒤 중복을 제거하여 좌표 압축한다.

각 나라를 처리할 때는 이분 탐색으로 $A_i+B_i$ 이상인 첫 번째 압축 좌표를 찾고, 그 위치부터 끝까지의 $D$의 최댓값을 구한다. 구간 최댓값 질의와 한 점 최댓값 갱신은 세그먼트 트리로 각각 $O(\log N)$에 처리할 수 있다.

정당성 증명

첫 $i$개의 나라를 처리한 뒤, 각 금화 $x$에 대하여 $D(x)$가 현재 금화가 $x$인 모든 가능한 상태 중 방문 횟수의 최댓값이라고 가정하자.

$i+1$번 나라를 방문하지 않는 모든 상태는 이전 상태와 금화와 방문 횟수가 모두 같으므로 기존의 $D$에 그대로 남는다.

$i+1$번 나라를 방문하는 상태를 생각하자. 방문 직전의 금화를 $x$라 하면 반드시

$$x\geq A_{i+1}+B_{i+1}$$

이어야 한다. 이러한 모든 이전 상태 중 방문 횟수의 최댓값은 구간 최댓값으로 구한 $M$이다. 나라를 방문하면 방문 횟수는 하나 증가하고 금화는 정확히 $B_{i+1}$개가 되므로, 이 경우의 최적값은 $M+1$이다.

따라서

$$D(B_{i+1})\leftarrow\max(D(B_{i+1}),M+1)$$

로 갱신하면 $i+1$번 나라를 방문하는 모든 경우와 방문하지 않는 모든 경우를 정확히 고려한다.

초기 상태 $D(C)=0$도 올바르므로, 수학적 귀납법에 따라 모든 나라를 처리한 뒤의 DP는 정확하다. 모든 $D(x)$ 중 최댓값이 정답이다.

복잡도

각 나라에서 이분 탐색, 구간 최댓값 질의, 한 점 갱신을 각각 한 번씩 수행한다.

따라서 시간 복잡도는 $O(N\log N)$이고, 공간 복잡도는 $O(N)$이다.

Solution written by GPT5.5