Help us understand the problem. What is going on with this article?

Fence Repair

More than 5 years have passed since last update.

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

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

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

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

で、できたのがコチラ。

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でいうと、ヒープキューアルゴリズムとかでしょうか。

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

ukisoft
まったり developer です。python と js を使うことが多いです。
rymansat
普段は宇宙開発に関わっていないサラリーマンが身近で誰でもできる宇宙開発を実現させることがリーマンサット・プロジェクト(Ryman Sat Project=rsp.)の目的です。キューブサットの開発をはじめ、宇宙を軸として様々なコミュニティやクリエイターとコラボレーションし、民間宇宙開発に関するネットワークを強化、拡張することを目指して活動しています。
https://www.rymansat.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした