Two Operations No.1 [yukicoder No.642]

https://yukicoder.me/problems/no/642

解法

https://yukicoder.me/submissions/233983

よくある方針に「順操作が難しそうなら、逆操作で考えてみる」という方針がある。
これで考えてみよう。
「-1」の逆操作は「+1」
「*2」の逆操作は「÷2（最下位ビットが0の時）」
これを使うと、Nを「+1」か「÷2」をして1にする最小操作回数となる。
あとは、アルゴリズムを考えてみると、なるべく小さくしたいので÷2を使いたいが、最下位ビットが0である必要があるため、最下位ビットが1なら+1をして最下位ビットを0にしてから、÷2をしよう。
貪欲にこれをやって、Nが1になったら終了。
操作回数を答えれば答え。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    int ans = 0;
    while (1 < N) {
        if (N % 2 == 1) N++, ans++;
        else N /= 2, ans++;
    }
    cout << ans << endl;
}