[JAVA] 백준 1527 완전탐색 (백트래킹)

 

 

 

1527번: 금민수의 개수

문제

금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다.

A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력하는 프로그램을 작성하시오.

풀이

이전에 백트래킹으로 문제를 풀어보았기 때문에 이번 문제도 한번 백트래킹으로 접근해보았습니다.

4와 7로만 이루어진 수를 만들어야 하기 때문에 현재 자리수에서 뒤에 4, 7를 계속 붙여나가면서 이미 최대 값을 벗어난 수는 더이상 탐색할 필요가 없기 때문에 탐색을 종료하고 다시 이전 DFS로 돌아오는 방식을 택했습니다.

📌 DFS

    public static void DFS(String now){
        if(Long.parseLong(now) > max) return;

        for(int i=0; i<2; i++){
            long target = Long.parseLong(now + value[i]);
            if(target >= min && target <= max){
                answer++;
            }
            DFS(now + value[i]);
        }

    }

• 재귀 형태로 현재 수에서 4 혹은 7을 계속 붙여나가면서 범위 내에있는 금민수인지 체크하여 값을 갱신해주었습니다.

📌 전체 코드

import java.util.*;
import java.io.*;

public class Main {
    static String[] value = {"4" , "7"};
    static int min;
    static int max;
    static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        min = Integer.parseInt(st.nextToken());
        max = Integer.parseInt(st.nextToken());

                // 첫 if문을 통과하기 위해 "0"으로 시작
        DFS("0");
        System.out.println(answer);
    }

    public static void DFS(String now){
        if(Long.parseLong(now) > max) return;

        for(int i=0; i<2; i++){
            long target = Long.parseLong(now + value[i]);
            if(target >= min && target <= max){
                answer++;
            }
            DFS(now + value[i]);
        }

    }

}

결과