N x Mのグリッドがあったとします。 自明ですが、マス目の数は N*M 個です。

これを K 個の長方形に分割することを考えるとき、 K 個の長方形の面積の差が高々 min(N, M) であり、各々の長方形の周の長さの和が最小となるような分割を行うアルゴリズムを求める。