백준 18511 자바 - 큰 수 구성하기 (BOJ 18511 JAVA)

문제 : boj18511

 

 

  N이 최대 1억이고, K의 각 원소는 1부터 9 까지이므로 어쨌든 8자리 수 이내로 모든 답이 나온다. 그리고 K는 최대 3개까지이므로 모든 경우를 봐도 최대 O(3^8) 이다. 따라서 따로 다른 방법 생각해볼 것 없이 브루트 포스로 풀면 된다. 약간의 백트래킹을 넣어서 예를들어 이미 N보다 큰 값이라면 더이상 볼 것 없이 종료하는 식으로 하면 된다. 백트래킹 개념을 넣지 않아도 시간내에 통과 가능한 간단한 문제이다.

 

 

코드 : github

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

public class Main {
    private int max = 0;
    private int n, k;
    private int[] arr;

    private void dfs(int cnt, int num) {
        if (cnt == 8) {
            return;
        }

        num *= 10;
        if (num >= n)
            return;

        for (int i = 0; i < k; i++) {
            int tmp = num + arr[i];
            if (tmp > n) continue;
            if (tmp > max) max = tmp;
            dfs(cnt+1, tmp);
        }
    }


    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        arr = new int[k];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < k; i++) arr[i] = Integer.parseInt(st.nextToken());

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

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}