던전 공략

현재 레벨이 $X$일 때 $A_i < X$인 던전만 고려하면 된다. 이 조건을 만족하지 않는 던전을 시도해도 레벨이 증가하지 않으므로, 나중에 시도하는 것보다 나을 수 없다.

$A_i < X$인 던전 중에서는 $B_i$가 가장 작은 던전을 고른다. 현재 레벨이 $X$이고 선택한 던전의 두 번째 난이도가 $B$라면, 공략 후 레벨은

$$X+\min(X,B)$$

가 된다. 현재 공략할 수 있는 두 던전의 두 번째 난이도가 $b \leq c$일 때, 두 던전을 $b,c$ 순서로 공략한 뒤의 레벨은 $c,b$ 순서로 공략한 뒤의 레벨 이상이다. 이 교환 논증을 반복하면, 현재 공략할 수 있는 던전 중 $B_i$가 가장 작은 던전을 먼저 골라도 최적해를 잃지 않는다.

던전을 $A_i$의 오름차순으로 정렬한다. 현재 레벨보다 $A_i$가 작은 던전의 $B_i$를 최소 힙에 넣고, 힙에서 최솟값을 꺼내 레벨을 갱신한다. 힙이 비어 있다면 남은 모든 던전에서 레벨을 올릴 수 없으므로 종료한다.

시간 복잡도는 $O(N\log N)$이고, 공간 복잡도는 $O(N)$이다. 최종 레벨은 $L+\sum B_i$ 이하이므로 이하이며, 부호 있는 64비트 정수 범위에 들어간다.

Solution written by GPT5