팬케이크 덱 timer 20s memory 1024MB

팬케이크는 보통 쌓아 올린 스택 형태로 제공되지만, 무한 팬케이크의 집(Infinite House of Pancakes)은 변화를 받아들인다! 이 식당의 새로운 홍보 포인트는 팬케이크를 덱(deque), 즉 양쪽 끝에서 꺼낼 수 있는 큐(double-ended queue)에서 제공하는 것이다.

당신은 이 식당의 서버이고, 당신의 일은 덱에 있는 모든 팬케이크를 손님들에게 서빙하는 것이다. 손님은 한 번에 한 명씩 도착하며, 각 손님은 팬케이크를 정확히 한 장 받는다. 당신은 각 손님에게 덱의 가장 왼쪽 또는 가장 오른쪽 팬케이크 중 하나를 서빙해야 하며, 선택은 당신에게 달려 있다. 팬케이크를 서빙하면 그 팬케이크는 덱에서 사라지고, 바로 옆에 있던 팬케이크가 새로 끝이 된다. 또는 팬케이크가 한 장만 남아 있다면 그 한 장을 서빙하는 수밖에 없고, 그렇게 하면 일이 끝난다!

각 팬케이크에는 맛있음 정도(deliciousness level)가 있다. 손님은 어떤 팬케이크를 받을지 선택할 수 없기 때문에, 각 손님은 자신이 받은 팬케이크가 이전의 모든 손님들이 받은 팬케이크들 각각의 맛있음 정도보다 작지 않을 때(즉 이전에 나온 모든 팬케이크의 맛있음 정도의 최댓값 이상일 때)에만 팬케이크 값을 지불한다. (첫 손님은 이전 손님이 없으므로 항상 지불한다.)

당신이 팬케이크를 서빙하는 순서를 최적으로 선택해, 값을 지불하는 손님 수를 최대화한다면 값을 지불하는 손님은 총 몇 명인가?