yukicoder No.643 Two Operations No.2

問題
No.643 Two Operations No.2 - yukicoder

解説
この解説は多分悪い例として見ていただくのが良いと思います。
考察のできる人は、公式解説通りに考えられるのでしょう。でも僕にはそんな思いつきはありませんでした。ならマシンパワーに頼るしかない、ということで、全探索解でACしました。これも競技プログラミングです。

操作1,2を様々な順番で実行して行って、x==yとなるような最小手順を探してみます。
問題はこの手順をどれくらいの深さまで見るかですが、適当に手元で実行すると、30回では時間がかかりすぎたので、20回にしました。

ans=10000と初期化しておいて、x==yになればctとの最小値を取ります。最終的にans==10000であれば、x==yにならなかったので-1を出力です。
今回は偶然答えが3以下になるような問題だったので、全探索が通って嬉しいですね。

#include <iostream>

using namespace std;
int ans=100000;
void dfs(int x,int y,int ct){
    //cout<<x<<y<<endl;
    if(ct>20){ //20回操作を試して見たら終了
        return;
    }
    if(x==y){
        ans=min(ans,ct);
        return ;
    }
    dfs(y,x,ct+1);  //操作１
    dfs(x+y,x-y,ct+1); //操作２
    return;
}
 
int main (){ 
    int x,y;
    cin>>x>>y;
    dfs(x,y,0);
    if(ans!=100000)cout<<ans<<endl;
    else cout<<-1<<endl;
    return 0;
}