[백준] 1526_가장큰금민수 / DFS 조합

 

 

Bronze

 

 

문제

 

은민이는 4와 7을 좋아하고, 나머지 숫자는 싫어한다.

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

N이 주어졌을 때, N보다 작거나 같은 금민수 중 가장 큰 것을 출력하는 프로그램을 작성하시오.

 

 

입력

 

첫째 줄에 N이 주어진다. N은 4보다 크거나 같고 1,000,000보다 작거나 같은 자연수이다.

 

 

출력

 

첫째 줄에 N보다 작거나 같은 금민수 중 가장 큰 것을 출력한다.

 

 

 

---

 

풀이

 

import java.util.*;

class Main {

    static ArrayList<Integer> list; // 금민수를 저장할 리슽트
    static int n; // 입력값
    
    // DFS 재귀적으로 금민수를 생성
    public static void dfs(int num){
        if(num >n) return;
        list.add(num);
        func(num*10+4); // 맨 뒷자리가 4인 금민수
        func(num*10+7); // 맨 뒷자리가 7인 금민수
        
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        list = new ArrayList<>();
        dfs(0); // n보다 작은 금민수들을 생성 (4와 7로만 이루어진 숫자의 조합을 구한다)
        Collections.sort(list,Collections.reverseOrder());

		int result=0;

        for(int i=0; i<list.size(); i++){
            if(list.get(i)<=n){
                result = list.get(i);
                break;
            }
        }
        
        System.out.print(result);
    }
}

 

 

해결 방법

1. dfs 깊이탐색을 사용해 4와 7로만 이루어진 숫자를 생성하고 리스트에 저장한다. (4와 7의 조합을 구한다)
2. 리스트에 저장된 금민수를 내림차순으로 정렬한다.
3. 리스트에서 n이하의 가장 큰 금민수를 찾아 리턴한다. 

 

---

 

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