[Java] 백준 1527 (금민수의 개수) 자바 문제 풀이

https://www.acmicpc.net/problem/1527

1527번: 금민수의 개수

 

알고리즘 분류

• 브루트포스 알고리즘

 

풀이

처음엔 완전탐색으로 하나씩 String으로 변환 후 체크했다.

하지만 메모리 초과가 발생하였고, 재귀 호출을 사용해 문제에 접근했다. 

 

핵심 로직이다. 

매개변수로 받은 n을 

어차피 한자리씩 늘어나니 10을 곱하고 7, 4를 더했다. ( 7 -> 77 or  74 )

왜냐하면 7와 4만 필요할 뿐 나머지는 필요가 없기 때문이다.

재귀호출을 빠져나오는 조건문은 b보다 크면 빠져나오도록 설정했다. 

public static void calculate(long n){
        if(n > b) return;
        if(a <= n){cnt ++;}
 
        long x = n * 10 + 7;
        long y = n * 10 + 4;
        calculate(x);
        calculate(y);
 
    }

 

 

 

아래는 전체 정답 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int a, b, cnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
 
        calculate(7);
        calculate(4);
 
        System.out.println(cnt);
 
    }
    public static void calculate(long n){
        if(n > b) return;
        if(a <= n) cnt ++;
 
        long x = n * 10 + 7;
        long y = n * 10 + 4;
        calculate(x);
        calculate(y);
 
    }
}