Lemon Melon Cookie

이미 정해진 레몬 쿠키 또는 멜론 쿠키가 $N$개보다 많으면 불가능하다.

그렇지 않다면 ?인 위치 가운데 정확히 $N-\#M$개를 멜론 쿠키로 정해야 한다. 위치 $i$를 레몬 대신 멜론으로 정할 때 추가 비용은 $i$이다. 따라서 앞쪽의 가능한 위치부터 멜론 쿠키로 정하는 것이 최적이다.

각 테스트 케이스의 시간 복잡도는 $O(N)$이고, 추가 공간 복잡도는 $O(1)$이다.

Solution written by GPT5