피자 탑 나누기 (Small)

< 그림: Designed by Kstudio / Freepik >

갑은 아주대학교 학생이다. 갑은 팔달관 1층에서 학과 개강총회를 준비하면서 피자 $N$ 판을 시켰다. 배달된 피자판은 식탁 위에 하나의 탑처럼 쌓여 있다. 갑은 높이가 $N$인 이 피자탑을 높이가 1인 피자탑 여러 개로 모두 나눠야 한다. 하기 싫은 일이지만 갑은 "피할 수 없다면 즐겨라"라는 로버트 엘리어트의 말을 떠올리고, 다음 놀이를 하면서 일을 끝내기로 했다.

놀이를 시작할 때 식탁 위에는 피자판 $N$ 개가 쌓인 탑 하나만 있다. 갑은 식탁 위의 피자탑 중 하나를 고른 다음, 고른 탑을 두 개의 탑으로 나눈다. 나눠진 두 탑의 높이가 각각 $B$와 $C$이면 갑은 이때 $B \times C$만큼 즐거움을 느낀다. 높이가 1인 탑은 더 나누지 않는다. 갑은 식탁 위에 나눌 수 있는 탑이 하나도 남지 않을 때까지 이 과정을 되풀이하고, 그 순간 개강총회 준비가 끝난다.

갑이 주문한 피자판의 수 $N$이 주어진다. 갑이 얻을 수 있는 즐거움의 총합의 최댓값을 구하시오.

< 높이가 8인 피자탑을 높이가 4인 피자탑 둘로 나누는 과정 >

첫째 줄에 피자판의 개수를 뜻하는 양의 정수 $N$ ($1 \le N \le 10$)이 주어진다.

갑이 얻을 수 있는 즐거움의 총합의 최댓값을 한 줄에 출력한다.

$N = 1$이면 시작부터 나눌 수 있는 탑이 없으므로 즐거움의 총합은 0이다.

$N = 3$인 경우를 살펴보자. ()는 피자탑 하나를 뜻하고, 괄호 안의 수는 그 탑의 높이다. 처음에 식탁 위에는 (3) 하나가 있다. 갑이 (3)을 (1)과 (2)로 나누면 $1 \times 2 = 2$만큼 즐거움을 느낀다. 이어서 높이가 2인 탑을 나눠 식탁 위를 (1), (1), (1)로 만들면 $1 \times 1 = 1$만큼 더 느낀다. 더 나눌 탑이 없으므로 총합은 $2 + 1 = 3$이다.