[BOJ / C++] 14606번 : 피자 (Small)

문제

< Picture: Designed by Kstudio / Freepik >

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

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

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

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

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

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

입력

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

출력

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

Solved.ac 레벨

실버 V

풀이

간단한 DP 문제였다.

우선, 높이가 n인 피자탑을 둘로 나눌 때 가장 큰 즐거움 값을 얻는 방법은 2로 나누는 것이다. 예를 들어 n = 5인 피자탑을 둘로 나누는 방법은 (1, 4), (2, 3) 두 가지가 있으며 둘 중 2로 나눈 값인 (2, 3)의 값이 6으로 (1, 4)의 4보다 큰 것을 확인할 수 있었다.

 

점화식은 간단한 과정을 통해 도출해낼 수 있었다.

먼저 n = 1일때, 즉 dp[1]은 0이다. 1개의 피자탑은 둘로 나눌 수 없고 즐거움을 얻을 수 없기 때문이다. 이어서 dp[2]는 1개씩 둘로 나눌 수 있고 1 * 1의 값은 1이다. 이 두 케이스는 점화식이 없어도 손쉽게 답을 도출해낼 수 있기 때문에 미리 초기화를 해주었다.

 

점화식을 구하기 위해 예제 중 n = 3인 경우를 그림과 식으로 나타내면 다음과 같다.

높이가 3인 피자탑을 2로 나눠 둘로 쪼개면 각각 높이가 1, 2인 피자탑으로 나눌 수 있고 두 피자탑을 다시 둘로 나누는 과정은 위의 dp[1]과 dp[2]의 값을 알아낸 것과 동일하다. dp[1]과 dp[2]의 합에 두 피자탑의 높이를 곱한 값을 더하면 dp[3]의 값을 알 수 있었다.

 

dp[3] = dp[1] + dp[2] + (1 * 2) = 3

 

위 식은 dp[4]와 dp[5]의 경우의 수를 더 살펴본다면 확실해지나 풀이에는 담지 않겠다. (그림을 그리기가 귀찮다..)

어쨌든 내가 도출해낸 점화식은 아래와 같다.

i >= 3 일 때,
int tmp = i / 2;
dp[i] = dp[tmp] + dp[i - tmp] + (tmp * (i - tmp));

도출해낸 점화식으로 코드를 작성해보자.

Code

#include<bits/stdc++.h>

using namespace std;

int n;
int dp[11];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    dp[1] = 0;
    dp[2] = 1;

    for(int i = 3; i <= n; i++) {
        int tmp = i / 2;

        dp[i] = dp[tmp] + dp[i - tmp] + (tmp * (i - tmp));
    }

    cout << dp[n] << "\n";

    return 0;
}

DP 잘하고싶다

 

14606번: 피자 (Small)