[BOJ]4演算(no.14395)

7269 ワード
BFS algorithm python boj テキストリンク

質問する


整数sを与えます.整数sの値をtに変換する最小演算回数を求めるプログラムを作成する.
使用可能な演算は次のとおりです.
s = s + s; (出力:+)
s = s - s; (出力:-)
s = s s; (出力:)
s = s/s; (出力:/)(sが0でない場合のみ使用可能)

入力


最初の行はsとtを与える.(1 ≤ s, t ≤ 109)

しゅつりょく


1行目に整数sをtに変換する方法を出力します.sとtが同じ場合は0を出力し、できない場合は−1を出力する.可能な方法が複数ある場合、出力は辞書順にリードします.
演算するアスキーコードの順序は「*」、「+」、「-」、「/」である.

🤔 の意見を打診


  • 優先順位のあるbfs!

  • 問題の演算子順にif文を並べます.

  • マイナスの場合は考えなくてもいいです.(s,tはいずれも1より大きい範囲を指定しているので、0を作成する必要はなく、最小値である可能性もありません.)

  • どのような順序で演算されているかを覚えておくため、キューにも演算子配列を1つ入れればよい.

  • キャッシュ配列の範囲は明確ではなく,s,tの最大範囲は10の9乗であるため,配列でキャッシュチェックを行うことはできない.(集合を使えばいい!)

    • 📌 説明する

    import sys
input = sys.stdin.readline

def main():
    def bfs(s,t):
        if s == t: return 0
        bound = 10e9
        cache = {s}
        q = [(s, "")]
        cnt = 0

        while q:
            tmp = []

            for i,hist in q:
                if i == t: return hist

                if (op := i*i) <= bound and op not in cache: 
                    tmp.append((op, hist+"*"))
                    cache.add(op)

                if (op := i+i) <= bound and op not in cache: 
                    tmp.append((op, hist+"+"))
                    cache.add(op)

                if (op := 1) not in cache:
                    tmp.append((op, hist+"/"))
                    cache.add(op)
            
            cnt += 1
            q = tmp

        return -1


    s,t = map(int, input().split())
    print(bfs(s,t))

if __name__ == "__main__":
    sys.exit(main())

    レビュー

  • 最近walrusキャリアと知り合って利用してみました!
  • バージョンは高いはずなので互換性はあまりよくありませんが、本当にきれいなコードが出てきました
    • JAVA基礎文法
    Do it! 複数の構成部品のサーフェスビューを作成するには