[JAVA]백준_18511_큰 수 구성하기

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

18511번: 큰 수 구성하기

문제 유형 : 브루트포스, 재귀

 

풀이 방식 : 

- 조건을 하나하나 따지면서 재귀로 풀어도 가능하지만 간단한 재귀로 푸는 방법을 다른 닝겐 소스를 참조해서 풀었음

Step 1. 먼저 입력 K 원소들을 정렬

Step 2. 재귀 함수로 0부터 시작하여 K의 원소들 중 큰 걸 넣어가면서 비교 now가 입력 값 N보다 크면 return, 작으면 비교 후 최대값 갱신

 

소스 코드

package BOJ;

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

public class BOJ_18511_큰수구성하기_Main {


	private static int[] num;
	private static int N;
	private static int K;
	private static int ans;

	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()," ");
		num = new int[K];
		for (int i = 0; i < K; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(num);
		dfs(0);
		System.out.println(ans);
	}

	private static void dfs(int now) {
		if(now>N) return;
		
		if(ans<now) ans=now;
		
		for (int i = K-1; i > -1; i--) {
			dfs(now*10+num[i]);
		}
	}

}