床全体を照らすのに必要なランプの最小数を求めるC++プログラム

n行m列のグリッドに区切られた床があるとします。この床全体をランプで照らすことを考えます。ランプは2つのセル(マス)の境界に設置でき、縦方向の境界に置いた場合はその左右の2つのセルを、横方向の境界に置いた場合はその前後の2つのセルを照らします。与えられたnとmに対して、床全体を照らすために必要なランプの最小個数を求めるのがこの問題です。

例えば、入力が n = 5、m = 3 の場合、出力は 8 になります。

解法のアプローチ

この問題は非常にシンプルな計算式で解くことができます。1つのランプが2つのセルを同時に照らせるため、必要なランプ数はセルの総数(n × m)を2で割った値になります。ただし、セルの総数が奇数の場合は切り上げが必要です。そこで、次の式を使用します。

res := (n * m + 1) / 2
return res

(n × m + 1) を 2 で割ることで、セルの総数が奇数の場合でも自動的に切り上げ処理が行われ、正しい最小ランプ数を求められます。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
#define N 100
int solve(int n, int m) {
   int res = (n * m + 1) / 2;
   return res;
}
int main() {
   int n = 5, m = 3;
   cout<< solve(n, m);
   return 0;
}

入力

5, 3

出力

8

計算例の確認

n = 5、m = 3 の場合、セルの総数は 5 × 3 = 15 です。このとき (15 + 1) / 2 = 8 となるため、答えは 8 になります。このように、整数除算の特性を活かしたシンプルな式で効率的に解答を得ることができます。