백준 18511 큰 수 구성하기 c++ (완전탐색)

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

18511번: 큰 수 구성하기

문제

N보다 작거나 같은 자연수 중에서, 집합 K의 원소로만 구성된 가장 큰 수를 출력하는 프로그램을 작성하시오. K의 모든 원소는 1부터 9까지의 자연수로만 구성된다.

예를 들어 N=657이고, K={1, 5, 7}일 때 답은 577이다.

입력

첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 원소는 1부터 9까지의 자연수다.

단, 항상 K의 원소로만 구성된 N보다 작거나 같은 자연수를 만들 수 있는 경우만 입력으로 주어진다.

출력

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

알고리즘 분류

• 브루트포스 알고리즘
• 재귀

풀이

순열 알고리즘을 이용한 완전 탐색 문제이다.

주어진 1개~ 3개의 원소는 중복이 허용되며, 이 원소들로 N보다 작은 수들을 구해야 한다.

순열 알고리즘으로 원소들로 만들 수 있는 모든 순열을 만들고, 그 중 N보다 크지 않은 수중 가장 큰 값을 구하면 된다.

인덱스 관리를 위해 n은 string으로 입력받는 게 편하다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
string n;
int answer;
string result;
void permutation(vector<int> vt) {
	if (result.length()>0 && stoi(n) >= stoi(result)) {
		answer = max(answer, stoi(result));
	}
	if (result.length() == n.length()) {
		return;
	}
	for (int i = 0; i < vt.size(); i++) {
		result += to_string(vt[i]);
		permutation(vt);
		result.pop_back();
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	
	int k;
	cin >> n >> k;

	vector<int> vt(k);
	for (int i = 0; i < k; i++) {
		cin >> vt[i];
	}
	
	permutation(vt);
	cout << answer;
	return 0;
}