[자바] 백준 18511번 큰 수 구성하기

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

 

DFS로 완전탐색 하는 문제를 너무 못하길래 무려 실버 5인 문제를 풀어봤는데 역시나.. 엣지 케이스에 싹 다 걸려서 계속 틀렸다. 사실 더 이상 무슨 반례가 있는지 모르겠어서 결국 구글링행.... 내일 다시 풀어보자 ^^

 

dfs 함수를 만들어서 내부에서 먼저 인수로 들어온 값이랑 n의 값을 비교해서 만약 인수 값이 더 크다면 그대로 return하고, 아니라면 answer의 값과 인수 값을 비교해서 answer의 값이 더 작다면 인수 값을 answer에 저장한다. 그리고 반복문을 돌리며, k 즉, 저장된 값의 개수만큼 돌리되, 큰 수부터 계산할 수 있도록 뒤에서부터 arr의 값을 가지고 와서 인수와 10을 곱한 값을 arr의 값과 더하고 이를 dfs에 넣으면 재귀적으로 동작하다가 결국, k보다 작거나 같은 수로 나올 수 있는 값 중 가장 큰 수가 나오게 된다.

 

import java.util.*;
import java.io.*;

public class Main {
    public static int n, k, answer;
    public static ArrayList<Integer> arr = new ArrayList<>();
    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());

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

        Collections.sort(arr);
        dfs(0);

        System.out.println(answer);
    }

    public static void dfs(int total){
        if(total > n) return;
        if(answer < total) answer = total;

        for(int i = k-1; i >= 0; i--){
            dfs(arr.get(i) + 10 * total);
        }
    }
}