[JAVA/DFS] 금민수의 개수_1527

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

1527번: 금민수의 개수

 

 

 

금민수의 개수 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

3702

1424

1190

39.960%

문제

은민이는 4와 7을 좋아하고, 나머지 숫자는 싫어한다. 금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다.

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

입력

첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력한다.

예제 입력 1 복사

1 10

예제 출력 1 복사

2

예제 입력 2 복사

11 20

예제 출력 2 복사

0

예제 입력 3 복사

74 77

예제 출력 3 복사

2

예제 입력 4 복사

1000000 5000000

예제 출력 4 복사

64

출처

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 브루트포스 알고리즘

 

 

• 브루트포스보다는 dfs로 풀면 쉽게 풀린다.

package baekjoon;

import java.util.Scanner;

public class Main {
	
	private static int answer = 0;
	
    public static void main(String[] args) {
    	
    	Scanner s = new Scanner(System.in);
    	
    	long A = s.nextLong(); // 최소
    	long B = s.nextLong(); // 최대
    	
    	int aTen = (int) Math.log10(A) + 1; // 자릿수 구하기
    	
    	// 초기값은 A의 자리수만큼 4로 채워서 시작.
    	StringBuffer start = new StringBuffer();
    	for(int i=0; i<aTen; i++) {
    		start.append("4");
    	}
    	long startNum = Long.parseLong(start.toString());
    	
    	// dfs 실행 : 단, 초기값이 B보다 작으면 애초에 시작도 하지 않음.
    	dfs(A, B, startNum, aTen);
    	System.out.println(answer);
    }
    
    public static void dfs(long min, long max, long num, int ten) {
    	// max를 초과했으면 더 진행하지 않음.
    	if(num > max) {
    		return;
    	}
    	// min보다 미만이면 answer을 더하지 않음.
    	if(num >= min) {
    		answer++;
    	}
    	
    	/*
    	 * 1의 자리수부터 아래 로직 수행
    	 * 1. 4이면 7로 바꾸고 break
    	 * 2. 7이면 4로 바꾸고 continue
    	 * 3. 맨 앞의 자리가 7이면 맨 앞에 4 추가 후 break
    	 * 
    	 * ex) 
    	 *  44 > 47 (1번)
    	 * 	47 > 44 (2번) > 74 (1번)
    	 *  77 > 74 (2번) > 44 (2번) > 744 (3번)
    	 */
    	long target = 1;
    	
    	for(int i=1; i<=ten; i++) {
    		target *= 10;
    		
    		long targetNum = (num%target) / (target/10);
    		
    		if(targetNum == 4) {
    			// (1번)
    			num += 3*(target/10);
    			break;
    		}
    		else if(targetNum == 7) {
    			// (2번)
    			num -= 3*(target/10);
    			if(i == ten) {
    				// (3번)
    				num += 4*target;
    				ten++;
    				break;
    			}
    		}
    		
    	}
    	
    	dfs(min, max, num, ten);
    	
    }
    
}