[백준, Java] 1527번, 금민수의 개수, (백트래킹)

문제 링크

1527번: 금민수의 개수

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 4와 7로만 이루어진 수를 금민수라고 합니다.

2. 수의 범위가 주어졌을 때 그 사이에 존재하는 금민수의 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 백트래킹을 통해서 범위에 존재하는 금민수를 탐색합니다.

 

3. 탐색을 통해 얻은 금민수의 개수를 결과로 출력합니다.

 

금민수 

 

4와 7로 이루어지는 수

 

44, 47, 444, 4744477....

 

금민수의 값들을 살펴보시면 이전 금민수에서 파생되는 것을 확인하실 수 있습니다.

 

금민수 4에서 파생되는 금민수 : 47, 44

 

금민수 44에서 파생되는 금민수 : 447, 444

 

...

 

파생되는 금민수의 경우를 점화식으로 표현하면

 

1. 현재 금민수 × 10 + 4

 

2. 현재 금민수 × 10 + 7

 

표현될 수 있으며, 이렇게 파생되는 금민수를 찾으면 모든 금민수를 탐색할 수 있습니다.

 

백트래킹(금민수 구하기)

 

금민수를 구하는 과정을 백트래킹을 통해서 탐색을 진행합니다.

 

 

백트래킹을 진행하면서, 진행되는 경우를 살펴보겠습니다.

 

1. 구한 금민수가 범위 최소값보다 작은 경우

 

▶ 해당 금민수의 개수를 세지 않고, 해당 금민수로 파생되는 다른 금민수를 탐색합니다.

 

 

2. 구한 금민수가 범위에 포함된 경우

 

▶ 해당 금민수의 개수를 세고, 해당 금민수로 파생되는 다른 금민수를 탐색합니다.

 

 

3. 구한 금민수가 범위 최대값보다 큰 경우

 

▶ 해당 금민수의 개수를 세지 않고, 해당 금민수로 파생되는 금민수도 범위보다 커지므로, 파생되는 금민수를 탐색하지 않습니다.

 

 

 

위 백트래킹 탐색을 종료하면, 범위 내 금민수의 개수를 구하실 수 있습니다.

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

A : 1

 

B : 10

 

2. 백트래킹을 통해서 범위에 존재하는 금민수를 탐색합니다.

 

금민수 시작 : 0

 

파생되는 금민수 : 4, 7

 

A(1) ≤ 금민수 ≤ B(10)을 4, 7이 모두 만족합니다.

 

 

금민수 시작 : 4

 

파생되는 금민수 : 44, 47

 

A(1) ≤ 금민수 ≤ B(10)을 44, 47이 모두 불만족합니다.

▶ 범위 최대값(10)보다 커져서, 더 이상 파생되는 금민수는 탐색하지 않습니다.

 

 

금민수 시작 : 7

 

파생되는 금민수 : 74, 77

 

A(1) ≤ 금민수 ≤ B(10)을 74, 77이 모두 불만족합니다.

▶ 범위 최대값(10)보다 커져서, 더 이상 파생되는 금민수는 탐색하지 않습니다.

 

 

 

3. 탐색을 통해 얻은 금민수의 개수를 결과로 출력합니다.

 

 

탐색을 통해 얻은 금민수 : 4, 7

 

 

2 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 금민수의 정보를 띄어쓰기 기준 나누었습니다.
• search를 이용하여 범위 내 금민수의 개수를 탐색합니다.
• 탐색한 금민수의 개수를 Bufferedwriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 백트래킹을 통해 범위 내 금민수의 개수를 진행합니다.

결과코드

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

public class Main {
    //금민수 값 개수
    static int cnt = 0;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //범위 값 저장
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        //범위 내 금민수 개수 구하기
        search(A, B, 0L);
        //금민수의 개수 BufferedWriter 저장
        bw.write(String.valueOf(cnt));		//결과 출력
        bw.flush();
        bw.close();
        br.close();
    }
    //백트래킹을 통해서 범위 내 금민수 값 구하는 함수
    static void search(int A, int B, long cur){
        //범위 최대값보다 클 때
        if(cur > B){
            return;
        }
        //범위 내 금민수의 값일 때
        if(cur >= A){
            cnt++;
        }
        //금민수 파생되는 값 탐색
        search(A, B, cur * 10 + 4);
        search(A, B, cur * 10 + 7);
    }
}