[JAVA]1527 금민수의 개수 (완전탐색)

  ✨  HINT

숫자를 아예 4,7로 구성해 보는 방식

숫자를 4,7로 구성한 후에 a와 b사이에 속하는지 확인하는 방식

 

 📚 문제  

1527번: 금민수의 개수

 

🔍 아이디어  

범위가 1~1,000,000,000이기 때문에 모든 수에 대해서 4,7로 이루어져 있는지 판단하는 것이 시간이 너무 오래 걸릴 것이라 생각하였습니다. 다른 방법은 아예 숫자 자체를 4,7로 이루어지게 한 후에 min, max사이에 해당 값이 있는지를 판단하는 것이 낫다고 생각하여 해당 방식을 이용하였습니다.

 

Int형의 범위가 2147483647까지 이기 때문에 길이가 10이상인 경우에 4,7로만 이루어진 수는 없어서 10<now.length()인 경우 바로 종료할 수 있도록 하였습니다. (11길이 이상은 int형 변환시 오류가 발생합니다)

이후에는 숫자가 min,max 사이에 있다면 가능한수를 1증가 시킵니다. 또한 만약 숫자가 max보다 크면 이후의 숫자는 의미가 없기때문에 바로종료합니다. 

 

숫자를 만드는 방법은

dfs(now + "4");
dfs(now + "7");

해당 부분으로 이전의 값에 +4, +7을 붙이면서 계속해서 탐색합니다.

 

 

📝 풀이 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj_1527_금민수의개수 {
    public static int max, small;
    private static int cnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        small = Integer.parseInt(st.nextToken());
        max = Integer.parseInt(st.nextToken());
        dfs("");
        System.out.println(cnt);
    }

    public static void dfs(String now) {
        if (10 <= now.length()) return;
        if (!now.equals("")) {
            int i = Integer.parseInt(now);
            if (small <= i && i <= max) {
//                System.out.println(i);
                cnt++;
            }
            if (max < i) return;
        }

        dfs(now + "4");
        dfs(now + "7");
    }
}