백준 BOJ 18511 - 큰 수 구성하기

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

재귀함수를 활용하는 문제.

3^9 = 19683 으로

그렇게 큰 범위의 숫자가 아니기 때문에

K를 선택해서 수를 구성하는 모든 경우의 수를 직접 탐색해봐도

시간초과 없이 문제를 해결할 수 있다.

 

재귀함수를 사용하는게 일반적이고 깔끔한 풀이이다.

재귀함수를 사용한 탐색 도중에 N의 범위를 넘어가는 경우

음수(-1) 등을 반환하도록

처리해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;

int N,M;
vector<int> K;

int recur(int val){
	if(val > N) return -1;
	
	int ans = val;
	for(auto k : K){
		ans = max(ans, recur(val*10 + k));
	}
	return ans;
}

int main(){
	int k;
	cin >> N >> M;
	for(int i=0; i<M; i++){
		cin >> k;
		K.push_back(k);
	}
	
	cout << recur(0);
	return 0;
}