문홍윤 멘토 timer 1.5s memory 1024MB

여러분은 가장 강력한 동물이 무엇이라고 생각하는가?

아마도 코끼리를 떠올릴 것 같다.

하지만 "문홍윤 멘토" 가 더 강력하다.

사실, 문홍윤 멘토는 지구를 파괴할 정도의 힘을 가지고 있다.

어느 날, 코끼리가 문홍윤 멘토에게 용감하게 지구를 지키기 위한 도전을 걸어 왔다.

생태계를 위협하는 대신 평화적인 방법으로 케이크를 먹는 도전이다.

힘만으로는 절대 문홍윤 멘토를 이길 수 없기 때문에, 코끼리는 규칙을 제시했다.

먼저, 케이크를 N조각으로 자른다.

i번째 조각은 A_i의 크기이며, i+1번 조각과 인접해 있다.

케이크는 원형이므로, N번 조각과 1번 조각 역시 인접해 있다.

또한, 모든 A_i는 서로 다르게 잘라져야 한다.

문홍윤 멘토가 먼저 첫 번째 조각을 원하는 대로 먹는다. (0.001초가 채 걸리지 않는다.)

그 뒤, 코끼리부터 번갈아 가면서 꺼낼 수 있는 조각 중 하나를 꺼내어 먹는다.

꺼낼 수 있는 조각은 인접한 조각 중 적어도 하나가 이미 제거된 조각을 의미한다.

이렇게 모든 조각을 먹을 때 까지 반복한다.

사실, 코끼리도 문홍윤 멘토도 딱히 전략을 쓸 생각은 없다.

그래서 둘 모두, 꺼낼 수 있는 조각 중에서는 무조건 더 큰 조각을 고른다.

이렇게 게임을 진행할 때, 그 결과는 문홍윤 멘토가 처음에 무슨 조각을 고르는 지에 달려 있다.

N개의 각 선택지에 대해 문홍윤 멘토가 최종적으로 먹게 될 조각의 크기 합을 구해보자.

(도전의 승패는 케이크와 상관 없이 문홍윤 멘토가 승리했다고 전해진다.)