백준 14607 피자 증명
수학 무지렁이의 증명 노트
2024.04.14
1) 문제
백준 14606, 14607 피자 문제
https://www.acmicpc.net/problem/14606
14606번: 피자 (Small)
예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작
www.acmicpc.net
https://www.acmicpc.net/problem/14607
14607번: 피자 (Large)
예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작
www.acmicpc.net
높이가 N 인 피자탑이 있을 때, 이 피자탑을 A와 B 높이로 분리하면 A*B 만큼 즐거움을 느낀다.
그리고 A 높이의 피자탑을 C와 D 높이로 분리하면 C*D 만큼 즐거움을 느낀다. 높이가 1이면 더 이상 분리할 수 없다.
더 이상 분리할 수 없을 때까지 피자탑을 반씩 분리해 나갈 때 즐거움의 총합을 최대화하는 방법 구하기
< 높이가 8인 피자탑을 높이가 4인 피자탑 둘로 분리시키는 과정 > [출처] 백준
2) 증명 시도
(1) 손으로 직접 분리해보았는데, 직관적으로는 당연히 절반씩 분리해야 제일 큰 값이 나올 거라고 생각했다. 왜냐하면 높이가 9라면 1과 8로 분리하면 1*8 =8이지만, 4와 5로 분리하면 4*5 = 20 이기 때문이다. 쪼개면 점점 더 작은 값만 나올 것이기에 초기에 큰 값을 구해둬야 결과적으로 제일 값이 커질 것이라고 생각했다. 그런데 이게 웬걸... [스포] 어떻게 쪼개도 결과 값이 같은 것이었다. 심지어 그 값은 1부터 n-1까지의 합이었다...
(2) 질문 게시판에 비슷한 의문을 품은 사람들이 있을 것이라 생각하고 봤더니, 유사한 질문글이 있었다.
https://www.acmicpc.net/board/view/20929
귀납법으로 증명할수 있습니다.
어떤 식으로 나누던간에 답은 n(n - 1)/2 됩니다.
n = 1인 케이스는 자명하고,
n > 1개를 k, m = n-k개로 나눈다고 했을때
답은 k(k - 1) / 2 + m(m - 1) / 2 + mk
= (k^2 - k + m^2 - m + 2mk) / 2
= ((k + m)^2 - k - m) / 2
= (n^2 - n) / 2
= n(n - 1)/2 가 됩니다.
증명하려고 하는 명제가 P(k) = k개의 피자를 나누는데 최대 즐거움 = k(k - 1)/2입니다.
P(k) 가 1~n - 1가 참이라고 가정했을때
n개를 k, n - k로 나누었으니 각각 k, n-k에 P(k), P(n - k)를 적용할 수 있죠.
그런데 내가 원한 건 이게 아니다... P(k) = k(k-1)/2 이고 P(m) = m(m-1)/2 라고 이미 가정을 하고 식을 전개해나갔는데, 나의 의문은 어째서 P(k) = k(k-1)/2 인가?!?!? 였다.
* 이와 비슷하게 증명을 정리해주신 분들이 있는데, 이 글들 또한 일단 n(n-1)/2 를 구하고 점화식에 대입해서 일반식을 찾는 흐름으로 이해했다.
https://casterian.net/algo-prob/boj14607.html
https://lighter.tistory.com/44
(3) 그러던 중 다른 접근방식의 증명을 발견하였다..!
https://beomsun0829.tistory.com/23
피자판 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
뭔가 가까워진 느낌이 들었지만, "쪼개는 수는 1 이상인 수면 모두 같은 값이 나온다고 가정하자." 이 부분이 역시나 아직 이해가 되지 않았다. 왜 같은 값일까??
(4) 1부터 n까지의 합이 어떤 원리인지부터 다시 파악해보면 힌트를 찾을 수 있겠다 싶어서 이번에는 문제의 증명이 아닌 1부터 n까지의 합을 검색 키워드로 넣고 탐색하였다. 그러다가 아래 글에서 1부터 n까지의 합을 삼각형 형태로 표현한 것을 보고 종이에 그려보다가 완전한 증명은 아니지만 뭔가를 발견한 것 같다.
[알고리즘] 1 ~ n까지 합을 구하는 원리
1 ~ n까지 합을 구하는 원리 관련글: 1부터 n까지의 합 구하기 전에 1 ~ n 까지 합 구하기 문제에 관해서 글을 올렸지만, 내용을 좀 더 보충하고자 합니다.그럼 1에서 n까지의 합을 구하는 문제에 대
adgw.tistory.com
위의 글에서 설명해주신 것은 1부터 n까지의 합은 삼각형의 넓이라는 것이었다.
○
○○
○○○
○○○○
○○○○○
그래서 삼각형을 그려보았다. 만약 처음 탑의 높이가 7이었다면, 1부터 6까지의 합이 답이었을 것이고, 그러면 1부터 6까지의 합 자체를 그림으로 표현하면 다음과 같을 것이다.
그러면 이를 만약 2와 5로 나눴다면 2*5를 제외하면 아래와 같이 남은 삼각형은 위의 삼각형과 오른쪽의 삼각형이 된다.
그러면 위의 형태에서 2*5를 빼고 나니 신기하게 1부터 4까지의 합과 1이 남은 것이었다.
만약 3과 4로 나눴다면 1부터 3까지의 합과 1부터 2까지의 합이 남았다.
f(7) = 3*4 + f(4) + f(3) 가 눈으로 보인 것이다.
이는 계속 쪼개들어가도 똑같이 적용된다. 위쪽의 삼각형이 높이가 4인 피자탑을 나눴을 때 즐거움의 총합인 1부터 3까지의 합인데, 이걸 만약에 2*2 로 쪼갰다면 위에 1개, 오른쪽에 1개가 남게 된다. 만약 1*3으로 쪼갰다면 윗부분에 1부터 2까지의 합만 남게 된다.
왜 그런 식이 나오게 된 건지 증명을 해낸 것은 아니었지만, 그 식을 도형으로 들여다보면 정말로 어떻게 쪼개나가도 합이 같다는 것을 눈으로 볼 수는 있었다. 이 문제가 출제된 배경에는 유사한 기출 문제나 유명한 정리같은 게 있었을 것 같은데 언젠가 찾게 되면 그 이름으로 꼭 증명을 찾아봐야겠다.