Treasure Hunt

$dp[i][0]$을 $1$번부터 $i$번 사람까지 방향을 정했고 $i$번 사람이 왼쪽을 볼 때 탐색 가능한 구간 길이의 최댓값이라 하자. $dp[i][1]$은 $i$번 사람이 오른쪽을 볼 때의 최댓값이다.

편의를 위해

$$A_0=B_0=0,\qquad A_{N+1}=L,\qquad B_{N+1}=0$$

으로 둔다. 초깃값은 $dp[0][0]=dp[0][1]=0$이다.

$i$번 사람이 왼쪽을 보는 경우를 생각하자. $i-1$번 사람도 왼쪽을 본다면 두 사람이 서로를 향해 탐색하지 않으므로 새로 더해지는 길이는 $\min(A_i-A_{i-1},B_i)$이다.

$i-1$번 사람이 오른쪽을 본다면 $i-1$번 사람이 두 사람 사이의 구간을 먼저 최대 $B_{i-1}$만큼 덮고 있다. 따라서 아직 덮이지 않은 길이는 $\max(0,A_i-A_{i-1}-B_{i-1})$이고, $i$번 사람이 새로 덮을 수 있는 길이는

$$\min(B_i,\max(0,A_i-A_{i-1}-B_{i-1}))$$

이다.

따라서

$$dp[i][0]=\max\left( dp[i-1][0]+\min(A_i-A_{i-1},B_i), dp[i-1][1]+\min(B_i,\max(0,A_i-A_{i-1}-B_{i-1})) \right)$$

이다.

$i$번 사람이 오른쪽을 본다면 새로 탐색하는 구간은 이전 사람들의 탐색 구간과 양의 길이로 겹치지 않는다. 따라서

$$dp[i][1]=\max(dp[i-1][0],dp[i-1][1])+\min(A_{i+1}-A_i,B_i)$$

이다.

정답은 $\max(dp[N][0],dp[N][1])$이다. 각 $i$마다 상수 번의 연산만 수행하므로 시간 복잡도는 $O(N)$이다.

Solution written by GPT5.6