상현이의 취미는 과자와 빵을 만드는 것이다. 오늘은 큰 맘 먹고 케익을 만들었다. 친구 형돈이가 놀러 와 있기 때문이다. 아래 그림처럼 케이크는 원형이다. N개의 조각으로 나누고 한 지점에서 시작하여 시계 반대 방향으로 번호를 붙였는데 우연히도 모두 다른 크기가 되었다.

이렇게 나누어진 N개의 케이크를 상현이와 형돈이는 나누어 먹기로 하였다. 나누어 먹는 방법은 아래와 같다.

- 손님인 형돈이가 먼저 선택한다. - 이후 상현이와 형돈이가 번갈아 가며 케이크를 선택한다. - 첫 조각을 형돈이가 선택한 후 상현이가 선택하는데 케이크가 무너지는 것을 방지하기 위하여 형돈이가 선택한 조각의 양쪽 조각중에서 큰 것을 선택한다.

위 그림의 예를 들면 형돈이가 1번 조각을 선택한 경우, 상현이는 2번, 5번 중에서 5번을 선택한다. 다음 형돈이는 2번 4번 중에 4번을 선택한다. 다시 상현이는 2번 3번 중에서 2번을 선택한다. 형돈이는 남은 3번 조각을 선택한다.

따라서 형돈이가 1번 조각을 첫 조각으로 선택한 경우 형돈이는 2 + 10 + 1 = 13 크기의 케이크를 먹게 된다. 형돈이는 문득 각 조각에 대해 그 조각을 첫 조각으로 선택할 때 먹게 되는 케이크의 전체 양이 궁금해졌다.

과제

케이크 조각의 수 N과 N개의 케이크 조각에 대한 크기의 정보가 주어질 때, 각 조각에 대하여 그 조각을 형돈이가 첫 조각으로 선택할 때 먹게 되는 케이크의 전체 양을 구하는 프로그램을 작성하시오.

#2808 upload 37 done 6 how_to_reg 5

케이크 나누기(cake) timer 1s memory 256MB

#2808

케이크 나누기(cake) 1s 256MB