Fence Repair

もっとエンジニア力つけたい！というわけで、ペーペーなプログラマを脱するべく、毎週Qiitaに投稿しようと思います。

で、今、社内でアルゴリズムの勉強会してるので、まずはそのコードを晒していこうと思います。
今回のお題はFenceRepair。
フェンスの修理を最小コストで行なえというやつです。

修理のために板を分割するのですけど、分割すると、分割前の板の長さのコストがかかります。
３０の板を、５、５、２０の長さに分割するとします。
まず、５、２５で分割すると、３０のコスト。
２５をさらに５と２０で分割すると、２５のコスト、合わせて５５のコストが必要となります。

インプットは、分割後の板の長さです（上記の例だと、５、５、２０）。
元の板の長さは、分割後の合計の長さと一致します。
この時のコストを最小にするアルゴリズムを考えよ！というわけです。

で、できたのがコチラ。

FenceRepair.php

class FenceRepair
{
    public static function calc($boardsLength)
    {
        $cost = 0;
        asort($boardsLength);
        while (count($boardsLength) > 1) {
            $firstBoard = array_shift($boardsLength);
            $secondBoard = array_shift($boardsLength);
            $cost += $newBoard = $firstBoard + $secondBoard;
            $boardsLength = FenceRepair::insertNumToArrayThroughAsort($newBoard, $boardsLength);
        }
        return $cost;
    }

    private static function insertNumToArrayThroughAsort($num, $array)
    {
        foreach ($array as $key => $value) {
            if ($value >= $num) {
                array_splice($array, $key, 0, $num);
                return $array;
            }
        }
        array_push($array, $num);
        return $array;
    }
}

切るたびに切る前の板の長さのコストがかかるので、切るときは、切った後の板の長さが、最も小さいものを選ぶ、ということを、逆算したような処理になってます。
insertNumToArrayThroughAsort()で毎回ソートしてるので、ちょっと無駄な処理をしてます。
heapSortを使えば、もうちょっとカッコよくなるらしいです。
Pythonでいうと、ヒープキューアルゴリズムとかでしょうか。

次は、もっとカッコよく・・・！