[C/C++] 백준 - 18511번 : 큰 수 구성하기

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보다 작거나 같은 자연수를 만들 수 있는 경우만 입력으로 주어진다.

 

---

 

주어진 집합 K 안의 수로 N보다 작거나 같은 수 중 가장 큰 수를 만들어야한다.

N의 값은 작지 않은 제한을 두었지만 K의 개수는 3개가 최대이다. 즉 완전탐색으로 모든 경우의 수를 확인해보아도 시간 내 통과가 가능하다.

 

나는 백트래킹 기법으로 모든 경우의 수를 확인하는 방법으로 문제를 해결하였다. 이렇게 해결하여도 0ms로 통과가 가능하다.

 

#include <algorithm>
#include <iostream>
#include <vector>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

using namespace std;

string to_N;
int N, K, answer;
vector<int> st, temp;

void input() {
	cin >> N >> K;
	st = vector<int>(K, 0);
	for (int i = 0; i < K; i++) {
		cin >> st[i];
	}
}

int returnValue() {
	int value = 0;
	for (int i = 0; i < temp.size(); i++) {
		value *= 10;
		value += temp[i];
	}
	return value;
}

void func() {
	int tempInteger = returnValue();
	if (temp.size() < to_N.size()) {
		answer = max(answer, tempInteger);
	}
	if (temp.size() == to_N.size()) {
		if (tempInteger <= stoi(to_N)) {
			answer = max(answer, tempInteger);
		}
		return;
	}

	for (int i = 0; i < K; i++) {
		temp.push_back(st[i]);

		func();

		temp.pop_back();
	}
}

void solution() {
	to_N = to_string(N);
	sort(st.begin(), st.end());
	for (int i = 0; i < K; i++) {
		temp.push_back(st[i]);

		func();

		temp.pop_back();
	}
	cout << answer << endl;
}

int main() {
	fastio;
	input();
	solution();

	return 0;
}