14607번: 피자(Large)

문제링크

문제

< Picture: Designed by Kstudio / Freepik >

갑은 아주대학교 학생입니다. 갑은 팔달관 1층에서 학과 개강총회를 준비하고 있습니다. 갑은 피자를 N 판 시켰습니다. 식탁 위에 피자 N 판이 탑처럼 쌓여있습니다. 갑은 높이가 N 인 이 한 피자탑을, 높이가 1인 피자탑들로 분리시켜야 합니다. 갑은 이 일을 하기 싫었습니다. 하지만 다음과 같은 격언이 있습니다.

“피할 수 없다면 즐겨라!” - 로버트 엘리어트

격언대로, 갑은 혼자 놀기를 하며 즐겁게 일을 해결하기로 합니다. 그래서 다음과 같은 놀이를 하기로 했습니다. 

먼저 놀이를 시작하기 전에, 식탁 위엔 N 개의 피자판이 하나의 탑으로 쌓여있습니다. 놀이가 시작되면, 갑은 식탁 위에 있는 피자탑들 중 하나를 고릅니다. 그리고 고른 피자탑을 두 개의 피자탑으로 분리합니다. 이때 갑은, 분리된 두 피자탑의 높이의 곱만큼 즐거움을 느낍니다. 즉, 갑이 고른 피자탑의 높이가 A이고, 갑이 이 피자탑을 높이 B인 피자탑과 높이 C인 피자탑으로 분리했다면, 갑은 이때 B * C만큼의 즐거움을 느낍니다. 단, 높이가 1인 피자탑은 더는 분리시키지 않습니다. 갑은 계속 피자탑들을 분리해나갑니다. 이 놀이를 하다가 식탁 위에 더 이상 분리할 수 있는 피자탑이 없어진다면, 갑의 개강총회 준비 일은 끝나게 됩니다. 

갑은 문득, 혼자 놀기를 통해 얼마나 재밌게 놀 수 있을지 궁금해졌습니다. 갑이 주문한 피자판의 수 N 이 주어질 때, 갑이 혼자 놀기를 통해 얻을 수 있는 즐거움의 총합의 최대값을 구해주세요.

< 높이가 8인 피자탑을 높이가 4인 피자탑 둘로 분리시키는 과정 >

입력

첫 번째 줄에는 피자판의 개수를 의미하는 양의 정수 N(1 ≤ N ≤ 109) 이 주어진다.

출력

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

---

처음엔 단순한 이분탐색문제라고 생각했다.

두 수를 쪼개서 곱할 때 최대가 되는 수는 

짝수일때 -> 반으로 쪼개서 곱한다 / 홀수일때 -> 반으로 나눈 값과 그 수에 1을 더하여 곱한다

가 최대가 될거라고 직관적으로 생각했었다. 그리고 메모리초과와 시간초과로 어려움을 겪고 있었을 때...

8을 4와 4로 쪼갤때 -> 28

8을 3과 5로 쪼갤때 ->28

8을 2와 6으로 쪼갤때 -> 28

.

.

.

어째선지 모두 같은 결과가 나와버린다?

또한 피자판의 개수가 10의 9승 만큼 주어진다. 상수 시간으로 풀릴 수 있는 문제라는 뜻이다. (약간의 편법이다)

긴 시간의 노력끝에, 마침내 최적화된 식을 만들어냈다.

결론부터 말하면,     n(n-1)/2  이다.

어떻게 이 식이 나올 수 있을까,

이를 증명해보도록 하자.

피자판 n개가 쌓여 있는 탑을 쪼개서 곱한 최대의 수를 f(n)이라고 하자, 또한 쪼갠 피자판의 두 높이를 a,b라고하자

f(n) = a*b + f(a) + f(b)      또한 a + b = n 이므로, b = n - a 이다.

f(n) = a*(n-a) + f(a) + f(n-a)

쪼개는 수는 1 이상인 수면 모두 같은 값이 나온다고 가정하자.

따라서 a = 1 , f(1) 삭제

f(n) = n-1 + f(1) + f(n-1) 

     = n-1 + f(n-1)

f(n-1) = n-2 + f(n-2)

f(n-2) = n-3 + f(n-3)

.

.

.

f(3) = 2 + f(2)

f(2) = 1 + f(1) = 1

그리고 f(n)부터 f(2) 까지 모든 함수를 뺀다 

f(n) = n-1 + n-2 + n-3 + n-4 ....  3 + 2 + 1

따라서 f(n) = n(n-1)/2

소스링크