ABC114 C-755

問題

C - 755

N以下の７５３数を出力する問題です。

けんちょん本４章章末問題です。

考察

再帰によるDFSで書いてきました。
生成した数，３，５，７を使ったかどうかどうかを示すフラグを引数にしました。

TLEするのとWAするケースがあります。

更に考えてみると N=10e9のケースではN*10がintの範囲を超えてしまいます。
#define int long long したらACしました。

コメント

再帰によるDFSはいろいろな応用ができそうです。
慣れないと組み方が難しいものもあるので，いろいろなパターンにあたって習熟したいと思います。

TLE/WAしたコード

#include <bits/stdc++.h>
using namespace std;
int n;
int cnt;
int f[3]={3,5,7};

void dfs(int x,int y, int z, int k){
  if(x>n) return;
  if(y*z*k != 0){
    //cout<<x<<" "<<y<<z<<k<<endl;
    cnt++;
  }
  for(int i=0;i<3;i++){
    if(i==0){
      dfs(x*10+f[0],1,z,k);
    }
    if(i==1){
      dfs(x*10+f[1],y,1,k);
    }
    if(i==2){
      dfs(x*10+f[2],y,z,1);
    }    
  }
}

int main() {
  cin>>n;
  dfs(0,0,0,0);
  cout<<cnt<<endl;
  return 0;
}