ニュータウン [パソコン甲子園2016 予選 D]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0338?year=2016

考察過程

1. 一見厄介そうな問題に見える
2. 問題を簡単にしているのが「全て同じ大きさの正方形」で埋めるという部分
3. とりあえず何かを全探索する方針で考えるが、正方形の一辺を全探索すると考えてみる
4. その一辺で埋めれるかの判定や答えの計算は高速にできるので、それでいけそう

解法

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0338/review/3140016/hamayanhamayan/C++14

埋めるのに使う全て同じ大きさの正方形の一辺lを全探索する。
その正方形で埋めれるのは、W,Hともにlで割り切れるとき。
そのとき、横W/l個、縦H/l個、正方形を並べるので、必要な正方形は(W/l)*(H/l)個。
あとは、1個につきコストCが必要なので、(W / l) * (H / l) * Cとなる。
全探索して、これの最小値が答え。
　
※ 大きい数の掛け算が出てくるときはオーバーフローを気にする必要があるが、今回は(10^3)^3=10^9なので大丈夫

int W, H, C;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> W >> H >> C;
    int ans = inf;
    rep(l, 1, 1010) if (W % l == 0 and H % l == 0) {
        int cst = (W / l) * (H / l) * C;
        chmin(ans, cst);
    }
    cout << ans << endl;
}