백준(BOJ) 16943번 숫자 재배치

알고리즘 풀이/백준(Boj)

100win10 2020. 5. 4. 14:43

16943번: 숫자 재배치

두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작거나 같으면서, 가장 큰 값을 구해보�

www.acmicpc.net

풀이 :

A의 크기는 10^9 미만 이므로 최대 8자리 밖에 가지지 않는다.

따라서 모든 경우를 하나하나 해봐도 시간 안에 가능하고 이는 next_permutation으로 처리하였다.

ans는 b보다 작은 값이면 갱신하게 된다.

코드 ( C++ )

	#include <iostream>
	#include <algorithm>
	#include <vector>
	#include <cmath>
	using namespace std;

	int main()
	{
	int a, b;
	cin >> a >> b;

	vector<int> A;

	while (a) {
	A.push_back(a % 10);
	a /= 10;
	}

	sort(A.begin(), A.end());

	int ans = -1;
	do {
	if (A[0] == 0) continue;

	int sum = 0;
	int d = (int)pow(10,A.size()-1);
	for (int i = 0; i < A.size(); ++i) {
	sum += A[i] * d;
	d /= 10;
	}

	if (sum <= b)
	ans = max(ans, sum);

	} while (next_permutation(A.begin(), A.end()));

	cout << ans << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub