남은 층의 수가 홀수일 때 행동하는 플레이어를 , 짝수일 때 행동하는 플레이어를 라고 하자.
의 최종 점수는 다음 그리디 알고리즘으로 구할 수 있다.
가장 위층의 원숭이 마리는 반드시 가 얻는다. 이후 나머지 층을 위에서부터 두 층씩 살펴본다. 새로 살펴본 두 층의 원숭이 수를 최대 우선순위 큐에 넣고, 큐의 최댓값을 꺼내 의 점수에 더한다. 선택되지 않은 값은 큐에 남겨 둔다. 가 짝수라면 가장 아래층 은 살펴보지 않는다.
가 홀수라면 는 Ishigami이고, 짝수라면 Iino이다. 모든 원숭이는 결국 한 플레이어의 점수가 되므로, 의 점수는 전체 원숭이 수에서 의 점수를 빼면 된다.
시간 복잡도는 , 공간 복잡도는 이다.
Proof
각 층을 아래에서 위로 나열하고, 에게 배정된 층은 (, 에게 배정된 층은 )로 나타내자.
앞에서부터 개의 괄호에 대해
Solution written by GPT-6
로 정의한다.
층이 짝수 개 남았다면 의 차례이며, 다음 조건을 만족하는 올바른 괄호열을 생각한다.
층이 홀수 개 남았다면 의 차례이며, 다음 조건을 만족하는 괄호열을 생각한다.
두 경우 모두 모든 접두 구간에 대해 조건이 성립해야 한다. 이러한 괄호열을 유효하다고 하자.
먼저, 는 임의의 유효한 괄호열에서 )에 배정된 원숭이 수의 합을 반드시 얻을 수 있음을 보이자.
의 차례라면 현재 괄호열은 , 을 만족한다.
높이가 처음으로 이 되는 위치를 라고 하자.
)이므로, 가장 아래층을 제거하여 해당 원숭이를 얻는다.))이다. 는 번째 층을 제거하여 바로 아래층과 합치고, 합쳐진 층을 )로 둔다.두 경우 모두 )에 배정된 점수를 잃지 않으면서 올바른 괄호열을 만들 수 있다. 두 번째 경우에는 이전의 높이가 음수가 아니고, 이후의 높이가 씩 증가하기 때문이다.
이제 의 차례라고 하자. 현재 괄호열은 올바른 괄호열이며, 의 행동에 따라 다음과 같이 대응한다.
(이다. 이를 제거하면 , 을 만족하므로 앞의 방법을 적용할 수 있다.((를 합치는 경우: 합쳐진 층을 (로 둔다. 역시 , 이 되며, )에 배정된 점수는 감소하지 않는다.() 또는 )(를 합치는 경우: 합쳐진 층을 )로 둔다. 같은 높이 조건을 만족하고, 기존에 (에 배정되었던 원숭이까지 )에 포함되므로 점수는 감소하지 않는다.))를 합치는 경우: 합쳐진 층을 )로 두고, 가 적절한 ((를 합치면 올바른 괄호열을 복원할 수 있다.마지막 경우를 자세히 보자.
가 합친 두 번째 )에 대응되는 (부터 시작하는 부분열은 다음과 같이 나타낼 수 있다.
여기서 는 각각 올바른 괄호열이며, 빈 문자열일 수도 있다.
가 마지막 ))를 합치고, 가 처음의 ((를 합치면 이 부분열은
가 되어 다시 올바른 괄호열이 된다. 가 합친 두 층은 모두 (에 배정되어 있었으므로, )에 배정된 점수는 감소하지 않는다.
따라서 가 어떤 행동을 하더라도 는 배정된 점수를 잃지 않으면서 유효한 괄호열을 유지할 수 있다. 게임이 끝나면 배정된 )가 모두 사라지므로, 는 처음 )에 배정된 원숭이 수의 합 이상을 얻는다.
반대로, 는 가 얻는 점수를 유효한 괄호열에서 가능한 최댓값 이하로 제한할 수 있다.
가 항상 가장 아래층을 제거하는 전략을 사용한다고 하자. 각 층을 실제로 제거한 플레이어에 따라 괄호를 배정한다.
가장 아래쪽 개 층을 생각하면, 이 구간에서 가 제거한 층의 수는 가 제거한 층의 수를 초과할 수 없다. 단, 가 먼저 행동한다면 최대 개 더 많을 수 있다. 이는 가 이 구간의 층을 제거하려면, 직전 의 차례에도 이 구간에 층이 남아 있어 가 가장 아래층을 제거했어야 하기 때문이다.
따라서 실제 제거 순서에 따라 만들어진 괄호열은 유효하다.
또한 가 제거한 층에 처음 매달려 있던 원숭이는 반드시 의 점수가 된다. 그러므로 가 얻은 점수는 )에 배정된 원숭이 수의 합을 초과할 수 없다.
두 결과를 결합하면, 의 최적 점수는 유효한 괄호열에서 )에 배정된 원숭이 수의 합의 최댓값과 같다.
이제 이 최댓값을 구하자.
유효한 괄호열에서 )의 전체 개수는
이며, 높이 조건을 반대로 해석하면 가장 위쪽 개 층에는 적어도
개의 )가 있어야 한다. 이 두 조건은 유효한 괄호열의 조건과 동치이다.
따라서 가장 위쪽 개 층에서 적어도 개, 가장 위쪽 개 층에서 적어도 개, 가장 위쪽 개 층에서 적어도 개를 선택해야 한다.
즉, 가장 위층을 먼저 선택하고 이후 두 층씩 추가로 살펴볼 때마다 하나의 층을 더 선택하면 된다.
이때 지금까지 살펴봤지만 아직 선택하지 않은 값 중 최댓값을 선택하는 것이 최적이다.
이를 교환 논법으로 보일 수 있다. 이전 단계까지 그리디와 일치하는 최적해에서, 현재 그리디가 선택한 값 가 선택되지 않았다고 하자. 그러면 현재까지 살펴본 층 중 아직 선택이 확정되지 않은 다른 값 가 선택되어 있어야 한다.
이므로 를 로 교체해도 점수는 감소하지 않는다. 이전 단계의 조건은 이미 확정된 선택으로 만족하며, 이후의 조건에서도 선택한 개수는 변하지 않으므로 유효성 역시 유지된다.
따라서 모든 단계에서 그리디의 선택과 일치하는 최적해가 존재하고, 최대 우선순위 큐를 이용한 알고리즘은 최적이다.