[PS] BOJ18511 큰 수 구성하기 ( DFS ) with JAVA

18511번: 큰 수 구성하기

 

◎ 문제풀이

 

개인적으로 DFS의 새로운 활용을 본 문제였다. 

 

정수 N과 k개의 9보다 작거나 같은 자연수가 주어졌을 때, k개로 만든 정수 중 N보다 작지만 최대인 정수를 구하는 문제이다. k개의 자연수의 조합으로 만들어진 경우의 수 중 최대인 정수를 구하는 문제이니, 이것도 '탐색' 문제이다.

 

k가 최대 3이고

N은 1억보다 작거나 같으니 최대 8자리 수이다. 

그러므로 나올 수 있는 경우의 수는 3⁸, 6561가지이다. 

 

시간제한은 1초이니 완전탐색으로 풀어도 되는 문제이다. k가 고정된 수가 아니므로 반복문보다는 DFS로 완전탐색 풀이를 하면 된다. 또한 모든 정수를 탐색하는 것이 아닌 N보다 작은 경우는 가지치기하는 백트래킹도 할 수 있다. 

 

그럼 DFS로 어떻게 경우의 수를 탐색해야 할까?

 

처음에는 정수의 가장 큰 자릿수부터 하나씩 정해가는 TOP-DOWN 방식으로 하려고 했으나, 이렇게 하면 정수N과 대소비교가 힘들어진다. 일의 자릿수부터 정해가는 BOTTOM-UP 방식은 경우의 수를 정수N가 비교할 수 있으니 더 좋은 방식이다. 

 

DFS 탐색의 회차가 올라갈 때마다, 10을 곱하여 자릿수를 올려나가는 것이다. N은 1억보다 작거나 같으니 DFS 탐색은 자릿수가 8자리가 되면 종료하면 된다. 

 

 

◎ 코드

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

import static java.lang.Math.*;

//BOJ18511 큰 수 구성하기
public class Main {
    static int[] nums;
    static int maxValue;
    static int k;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        nums = new int[3];

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<k;i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0,0); // DFS 시작
        System.out.println(maxValue);

    }

    public static void dfs(int value,int depth){

        if( depth == 8 ) return; // 자릿수가 8자리이면 종료
        value *= 10; // 자릿수 올리기

        for(int i=0;i<k;i++){
            int tmp = value + nums[i];// 일의 자리에 k개의 자연수 중 하나 넣기
            if(tmp > n) continue; // n보다 큰 경우 가지치기 ( 백트래킹 )
            maxValue = max(maxValue,tmp); // 최대값 최신화
            dfs(tmp,depth+1); // 자릿수 올리고 DFS 탐색
        }
    }
}