C++で解く！N回のカットで得られる最大ピース数の求め方

問題概要

1枚の正方形のピースに対して、合計N回の水平方向または垂直方向のカットを加えるとき、同じ大きさの正方形・長方形のピースを最大でいくつ作れるかを求めるのがこの問題です。

まず、具体例を使って問題の内容を確認していきましょう。

例1

入力 − N = 8

出力 − 25

説明 − N = 8 の場合、垂直方向のカット数は4回、水平方向のカット数は4回となります。

合計ピース数 = 25

例2

入力 − 7

出力 − 20

アルゴリズムの考え方

• カットの総数Nが与えられたとき、ピース数を最大化するには、水平方向と垂直方向のカット数をできるだけ均等に分配する必要があります。

  Nが偶数であれば水平・垂直ともに同数のカットとなり、Nが奇数であればどちらか一方が他方より1回多くなります。

  したがって、水平方向のカット数 = N/2、垂直方向のカット数 = N−H と表せます。

• 関数MaxPieces()の中で、水平方向のカット数を格納するint型変数Hを N/2 で初期化します。

• 続いて、垂直方向のカット数を格納するint型変数Vを N−H で初期化します。

• H回のカットで区切られる行は H+1 本、V回のカットで区切られる列は 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