[BOJ]白俊1463号1(Python)に作成



質問する


整数Xに使用できる演算は3種類あります.
  • Xを3で割って3で割った.
  • Xを2で割って2で割った.
  • 1を減算します.
  • 整数Nが与えられると、上記3つの演算を適宜用いて1が作成される.使用演算回数の最大値を出力してください.

    入力


    第1の行は、1以上、106以下の整数Nを与える.

    しゅつりょく


    1行目の演算回数の最大値を出力します.


    入力します。

    2

    出力します。

    1

    入力します。

    10

    出力します。

    3

    に答える

    
    def DFS(X, cnt):
        global rst
        if cnt >= rst or X < 1:
            return
        elif X == 1:
            rst = min(rst, cnt)
        cnt += 1
    
        if X % 3 == 0:
            DFS(X // 3, cnt)
        if X % 2 == 0:
            DFS(X // 2, cnt)
        DFS(X - 1, cnt)
    
    
    if __name__ == "__main__":
        X = int(input())
        rst = X
        DFS(X, 0)
        print(rst)