링크
14607번: 피자 (Large)
예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작
www.acmicpc.net
※ 14606번과 14607번은 입력 범위를 제외하고는 동일한 문제입니다.
문제
갑은 아주대학교 학생입니다. 갑은 팔달관 1층에서 학과 개강총회를 준비하고 있습니다. 갑은 피자를 N 판 시켰습니다. 식탁 위에 피자 N 판이 탑처럼 쌓여있습니다. 갑은 높이가 N 인 이 한 피자탑을, 높이가 1인 피자탑들로 분리시켜야 합니다. 갑은 이 일을 하기 싫었습니다. 하지만 다음과 같은 격언이 있습니다.
“피할 수 없다면 즐겨라!” - 로버트 엘리어트
격언대로, 갑은 혼자 놀기를 하며 즐겁게 일을 해결하기로 합니다. 그래서 다음과 같은 놀이를 하기로 했습니다.
먼저 놀이를 시작하기 전에, 식탁 위엔 N 개의 피자판이 하나의 탑으로 쌓여있습니다. 놀이가 시작되면, 갑은 식탁 위에 있는 피자탑들 중 하나를 고릅니다. 그리고 고른 피자탑을 두 개의 피자탑으로 분리합니다. 이때 갑은, 분리된 두 피자탑의 높이의 곱만큼 즐거움을 느낍니다. 즉, 갑이 고른 피자탑의 높이가 A이고, 갑이 이 피자탑을 높이 B인 피자탑과 높이 C인 피자탑으로 분리했다면, 갑은 이때 B * C만큼의 즐거움을 느낍니다. 단, 높이가 1인 피자탑은 더는 분리시키지 않습니다. 갑은 계속 피자탑들을 분리해나갑니다. 이 놀이를 하다가 식탁 위에 더 이상 분리할 수 있는 피자탑이 없어진다면, 갑의 개강총회 준비 일은 끝나게 됩니다.
갑은 문득, 혼자 놀기를 통해 얼마나 재밌게 놀 수 있을지 궁금해졌습니다. 갑이 주문한 피자판의 수 N 이 주어질 때, 갑이 혼자 놀기를 통해 얻을 수 있는 즐거움의 총합의 최댓값을 구해주세요.
입력
첫 번째 줄에는 피자판의 개수를 의미하는 양의 정수 \( N ( 1 \leq N \leq 10^9 ) \) 이 주어진다.
※ 14606번에서는 N의 범위가 \( N ( 1 \leq N \leq 10 ) \) 입니다.
출력
갑이 얻을 수 있는 즐거움의 총합의 최댓값을 한 줄에 출력한다.
풀이
DP를 사용할 수도 있지만, 이를 응용해 일반항을 만들면 쉽게 풀이할 수 있습니다.
피자판의 갯수를 \( n \)이라고 하고, 떼어낼 피자판의 갯수를 \( a (a>1) \) 라고 가정합시다.
피자판을 \( n-a \)개와 \( a \)개로 나눌 때 최대로 얻을 수 있는 즐거움의 총합은 몇일까요?
다음 두 가지 방법으로 계산해봅시다.
i) \( a \)개를 바로 떼어내서 \( n-a \)개와 \( a \)개로 분리하는 경우
이 때 얻는 즐거움은 \( (n-a) * a \) 입니다.
ii) 1개씩 \( a \)번 떼어내서 \( n-a \)개와 1개, 1개, ... 으로 분리하는 경우
맨 처음에는 \( n-1 \)개와 1개로 분리되므로 이 때 얻는 즐거움은 \( (n-1) \) 입니다.
그 다음에는 \( n-1 \)개를 \( n-2 \)개와 1개로 분리하므로 \( (n-2) \) 의 즐거움을 얻습니다.
이를 \( a \)회 반복하면, 총 \( (n-1) + (n-2) + \cdots + (n-a) \) 의 즐거움을 얻게 됩니다.
i)에서 얻는 즐거움은 \( (n-a) * a \), ii)에서 얻는 즐거움은 \( (n-1) + (n-2) + \cdots + (n-a) \) 이므로, a>1을 이용하여 이를 비교하면
$$ a > 1 $$
$$ 2a > a+1 $$
$$ 2a^2 > a(a+1) $$
$$ a^2 > \frac{a(a+1)}{2} $$
$$ an - a^2 < an - (1 + 2 + \cdots + a) $$
$$ (n-a) * a < (n-1) + (n-2) + \cdots + (n-a) $$
이므로, 1개씩 분리하는 ii)의 방식이 더 즐거움을 많이 얻게 된다는 것을 유도할 수 있게 됩니다.
그러면, 모든 피자판을 다 떼어낼 때는 \( a = n \) 인 경우이므로 ii)의 방식에서 얻는 총 즐거움을 \( F(n) \) 이라고 한다면
$$ F(n) = (n-1) + (n-2) + \cdots + (n-n) = \frac{n(n-1)}{2} $$
이 일반항으로 도출됩니다.
이외에도 예제를 보고 유추하는 방법이나, \( F(n) \) 과 \( F(n-1) \) 의 관계를 이용해서 DP를 사용하는 방법도 사용할 수 있겠습니다.
$$ F(n) = F(n-1) + (n-1) $$
코드
a = int(input())
print(int(a*(a-1)//2))난이도
2022년 1월 2일 기준 14606번의 난이도는 실버 4, 14607번의 난이도는 실버 3입니다.
일반항을 구하면 쉬워진다는 점을 감안해 해당 난이도들에서 -1한 값으로 기여했습니다.
'프로그래밍 > PS' 카테고리의 다른 글
| 「BOJ 27514」 1차원 2048 (0) | 2024.03.23 |
|---|---|
| 「BOJ 4463」 피보나치 수 분석 (0) | 2022.01.15 |
| 「BOJ 12871」 무한 문자열 (0) | 2022.01.08 |
| 「BOJ 23888」 등차수열과 쿼리 (0) | 2022.01.05 |
