[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)