755 [AtCoder Beginner Contest 114 C]

atcoder.jp

7,5,3 がそれぞれ1個以上含まれている数を 753数 と呼ぶ。1以上N以下の整数のうち、753数は何個あるか。

N が 10^9 なので全探索は不可能です。そこで、再帰関数を用いて 7,5,3 のみで構成されるN以下の数字を全て作っていき、その中から753数の個数を調べるという方法をとります。

全探索ができない→アルゴリズムを見直す、というパターンはお決まりですが、全探索ができない→探索個数自体を減らす、というパターンは初めて見たような気がします。勉強になりました。あと、再帰関数の使い方も。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	
	static int ans = 0;
	static int n;

	public static void main(String[] args) {
		
		n = sc.nextInt();
		f753(0L);
		System.out.println(ans);
		
	}

	static void f753 (long x) {
		if (x > n) {
			return;
		}
		else {
			String temp = String.valueOf(x);
			if (temp.contains("7") && temp.contains("5") && temp.contains("3")) {
				ans++;
			}
		}
		f753(x*10 + 7);
		f753(x*10 + 5);
		f753(x*10 + 3);
	}

}

・7 - 5 - 3
・77,75,73 - 57,55,53 - 37,35,33

という手順で 7,5,3 のみで構成される数字を作り、7,5,3 全てが含まれているなら答えのカウントを増やします。