⭕️[BOJ] 18511 - 큰 수 구성하기

문제 링크

18511-큰 수 구성하기

입력

첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 원소는 1부터 9까지의 자연수다.
단, 항상 K의 원소로만 구성된 N보다 작거나 같은 자연수를 만들 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 N보다 작거나 같은 자연수 중에서, K의 원소로만 구성된 가장 큰 수를 출력한다.

문제 풀이

재귀로 푸는 건 알겠는데 너무 복잡해져서 다른분의 소스 참조

일단 원소들을 정렬한 후 원소들의 큰값을 넣어가며 n과 비교하여 크면 return, 작으면 최대값 갱신
이거는 이해할 수 있는데 다시 풀라면 못 풀 것도 같아서
비슷한 문제 풀어보면서 더 연습해야겠다.

참조한 코드
(코드에 대한 설명은 따로 없음)

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

public class Main {

    static int n, k, ans;
    static int[] kArr;

    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());

        kArr = new int[k];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < k; i++) {
            kArr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(kArr);
        dfs(0);
        System.out.println(ans);

    }

    public static void dfs(int num) {
        if(num >  n) return;

        if(ans < num) ans = num;

        for (int i = k - 1; i >= 0; i--) {
            dfs(num * 10 + kArr[i]);
        }
    }
}