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

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

---

문제

---

아이디어

초기에는 입력받은 N의 각 자릿수와 K의 원소를 비교하며 순차적으로 탐색했다. 하지만, 이 방법으로 구현하게되면 N을 문자열로 변환하여 계산하기에 아래와 같은 입력에서 제대로된 값을 얻을 수 없다.

4311 3
4 8 9

 

위 입력을 받았을 때, 각 자릿수와 순차적으로 비교하면 맨 앞자리인 '4'와 K의 원소 '4'를 대응시키게 되는데, 이는 우리가 원하는 답이 아니다. 우리는 위 상황에서 최대로 만들 수 있는 수가 '999' 인 것을 알기에 다른 방법을 생각해야했다.

 

두번째 방법은 K의 원소로 만들 수 있는 모든 수를 구하고, 이의 최댓값을 찾는 것이다.

 

위 방법을 위해 dfs 를 사용하기로 했다. 

K의 원소를 노드로 생각하고, String 형태로 숫자를 하나씩 붙여가며 N보다 작은 모든 수를 찾는다.

 

아래와 같이 arr[] 에는 K의 원소들을 넣어두고, num에다가 하나씩 붙여 이를 N보다 작은 모든 수들에 대해 최댓값을 기록하면 된다.

for(int i=0; i<k; i++) {
    dfs(Integer.parseInt(num+"" + arr[i]+""));
}

 

위 코드는 이런 식으로 동작된다.

4311 3
4 8 9

dfs(4) -> dfs(44) -> dfs(444) -> dfs(4444) (N보다 크므로 return) -> dfs(4448) (N보다 크므로 return) -> ... dfs(448) -> ...

위 방법대로 진행하며 최댓값을 기록한다.

---

전체 코드

package Baekjoon;

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

public class B_18511 {
    static int n, k, max;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // N, K 입력
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        // K원소 배열
        arr = new int[k];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < k; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        // K원소 배열 정렬
        Arrays.sort(arr);

        max = 0;
        dfs(0);
        System.out.println(max);
    }

    static void dfs(int num) {
        // num이 n보다 크면 리턴(스택에서 제거)
        if(num > n) return;

        max = Math.max(max, num);

        for(int i=0; i<k; i++) {
            dfs(Integer.parseInt(num+"" + arr[i]+""));
        }
    }
}