C++에서 N번의 절단으로 얻을 수 있는 최대 조각 수 구하기

문제 개요

주어진 정사각형 조각을 가로 또는 세로 방향으로 총 N번 잘랐을 때, 동일한 크기의 정사각형 또는 직사각형 조각을 최대 몇 개까지 얻을 수 있는지 계산하는 것이 이번 과제입니다.

예시로 이해하기

입력 − N = 8

출력 − 25

설명 − N이 8일 때 세로 절단은 4번, 가로 절단은 4번입니다.

총 조각 수 = 25개

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

입력 − 7

출력 − 20

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

접근 방법

절단 횟수 N이 주어졌을 때 결과 조각 수를 최대화하려면 가로 절단과 세로 절단의 횟수를 최대한 균등하게 배분해야 합니다.
N이 짝수라면 가로와 세로 절단 횟수가 같아지고, N이 홀수라면 어느 한쪽이 다른 쪽보다 1회 더 많아집니다.
따라서 가로 절단 수 = N/2, 세로 절단 수 = N − H로 정할 수 있습니다.
MaxPieces() 함수에서는 int형 변수 H에 N/2 값을 저장하여 가로 절단 횟수를 관리합니다.
int형 변수 V에는 N − H 값을 저장하여 세로 절단 횟수를 관리합니다.
최종 조각 수 = (가로 줄 수) × (세로 줄 수) = (H + 1) × (V + 1)

공식이 성립하는 이유

정사각형은 처음에 1개의 행과 1개의 열로 이루어져 있습니다. 가로 절단을 한 번 할 때마다 행이 하나씩 늘어나고, 세로 절단을 한 번 할 때마다 열이 하나씩 늘어납니다. 따라서 가로 절단 H번과 세로 절단 V번을 실행하면 (H + 1)행 × (V + 1)열의 격자가 만들어지고, 전체 조각 수는 (H + 1) × (V + 1)이 됩니다.

두 수의 합이 고정되어 있을 때는 두 수가 서로 가까울수록 곱이 커집니다(산술-기하 평균 부등식). 그래서 가로와 세로 절단 횟수를 균등하게 나누는 것이 최대 조각 수를 보장합니다.

C++ 코드 예제

#include <bits/stdc++.h>
using namespace std;
int MaxPieces(int N){
    // H는 가로 절단 횟수
    int H = N / 2;
    // V는 세로 절단 횟수
    int V = N - H;
    // 최대 조각 수 = (H + 1) * (V + 1)
    return ((H + 1) * (V + 1));
}
// 메인 함수
int main(){
    // 절단 횟수
    int N = 7;
    cout << "Max pieces = " << MaxPieces(N);
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과를 얻습니다 −

Max pieces = 20