จำนวนชิ้นสูงสุดจากการตัด N ครั้งใน C++

ภาพรวมปัญหา

คำนวณจำนวนชิ้นสี่เหลี่ยมจัตุรัส/สี่เหลี่ยมผืนผ้าขนาดเท่ากันสูงสุด ที่ได้จากการตัดกระดาษสี่เหลี่ยม N ครั้ง (ตัดแนวนอนหรือแนวตั้ง)

ตัวอย่าง

Input: N = 8
Output: 25
Explanation: ตัดแนวตั้ง 4 ครั้ง, แนวนอน 4 ครั้ง -> (4+1)×(4+1) = 25 ชิ้น

Input: N = 7
Output: 20
Explanation: ตัดแนวตั้ง 3, แนวนอน 4 -> (3+1)×(4+1) = 20 ชิ้น

หลักการ

• เพื่อให้ได้ชิ้นมากที่สุด ต้องตัดแนวนอนและแนวตั้งให้เท่ากันที่สุด
• ถ้า N คู่: แนวนอน = แนวตั้ง = N/2
• ถ้า N คี่: แนวนอน = N/2, แนวตั้ง = N - N/2 (หรือกลับกัน)
• จำนวนชิ้น = (แนวนอน + 1) × (แนวตั้ง + 1)

ตัวอย่างโค้ด C++

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

int MaxPieces(int N) {
    int H = N / 2;      // Horizontal cuts
    int V = N - H;      // Vertical cuts
    return (H + 1) * (V + 1);
}

int main() {
    int N = 7;
    cout << "Max pieces = " << MaxPieces(N);
    return 0;
}

ผลลัพธ์

20