C++로 구현하는 직사각형 k번 자르기 문제: 최소 조각 면적의 최댓값 찾기

이 글에서는 C++를 이용해 주어진 직사각형을 정확히 k번 잘랐을 때, 만들어지는 가장 작은 조각의 면적이 최대가 되도록 하는 값을 구하는 방법을 다룹니다.

문제의 조건은 다음과 같습니다. 직사각형의 두 변의 길이와 자를 수 있는 횟수 k가 주어지며, 각 컷은 하나의 조각을 두 개로 나눕니다. 우리의 목표는 k번의 컷을 모두 사용한 후 남는 조각 중 가장 작은 것의 면적을 최대화하는 것입니다.

해결 아이디어

핵심 로직은 다음과 같습니다.

• 컷 횟수 k가 (n + m - 2)보다 크면 더 이상 자를 수 없으므로 "Not possible"을 출력합니다.
• k가 max(m, n) - 1보다 작은 경우, 한 방향으로만 균등하게 나누는 것이 유리합니다. 이때 결과는 max(m * (n / (k + 1)), n * (m / (k + 1)))가 됩니다.
• 그 외의 경우에는 두 방향을 모두 활용해야 하며, 결과는 max(m / (k - n + 2), n / (k - m + 2))로 계산됩니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

void max_area(int n, int m, int k) {
    if (k > (n + m - 2))
        cout << "Not possible" << endl;
    else {
        int result;
        if (k < max(m, n) - 1) {
            result = max(m * (n / (k + 1)), n * (m / (k + 1)));
        }
        else {
            result = max(m / (k - n + 2), n / (k - m + 2));
        }
        cout << result << endl;
    }
}

int main() {
    int n = 3, m = 4, k = 1;
    max_area(n, m, k);
    return 0;
}

실행 결과

위 코드에서 가로 4, 세로 3인 직사각형을 1번 잘랐을 때, 가장 작은 조각의 면적 최댓값은 다음과 같습니다.

6

즉, 4×3 직사각형을 한 번 잘라 두 조각으로 나눌 때, 작은 조각의 면적이 최대 6(예: 3×2와 3×2로 분할)이 되도록 자르는 것이 최선입니다.