[백준] 피자(Small) C++ 풀이

---

알고리즘 분류

• 수학
• 다이나믹 프로그래밍

---

문제 설명

< Picture: Designed by Kstudio / Freepik >

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

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

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

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

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

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

---

입력 설명

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

 

---

출력 설명

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

---

예제 입력

1

3

5

8

---

예제 출력

0

3

10

28

---

아이디어

피자탑의 높이가 0이나 1이라면 더이상 나눌 수 없으므로 0을 리턴하고 아니라면 가장 크게 쪼갤 수 있는 부분으로 쪼개서 그 값을 곱하고 기존 값에 더해준다.

---

알고리즘

n이 0이나 1이라면 더이상 쪼갤 수 없으므로 0을 리턴한다.

n이 0이나 1이 아니라면 n이 짝수라면 중간인 n/2로 반으로 나누고 n이 홀수라면 n/2과 n/2+1로 나눠서 그 둘을 곱하고 

재귀 함수를 실행한다. 이를 반복하여 최종적으로 합산된 값을 출력한다.

---

코드

#include <iostream>
using namespace std;
int divcon(int n)
{
	if(n==0 || n==1) return 0;
	if(n%2==0) return ((n/2) * (n/2)) + (divcon(n/2) + divcon(n/2));
	return ((n/2) * (n/2+1)) + (divcon(n/2) + divcon(n/2+1));
}
int main()
{
	int n; cin>>n;
	cout<<divcon(n);
	return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/14606

문제를 보자마자 divide and conquer 전략으로 푸는 문제임을 직감했다.

divide and conquer란 바로 해결 할 수 없는 큰 문제를 작은 문제로 나누어서 재귀적으로 해결하여 합치는 방법이다.

그래서 n을 계속 절반으로 쪼개고 쪼갠 값을 곱하여서 더하는 방식으로 문제를 해결했다.

문제를 푼 이후에 보니까 다이나믹 프로그래밍을 사용하는 문제여서 다음에는 다이나믹 프로그래밍을 사용해서도 풀어보고싶다는 생각을 했다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!