DOJ

해설

$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