์•Œ๊ณ ๋ฆฌ์ฆ˜

  • DP ์‚ฌ์šฉ.
  • bottom-up ๋ฐฉ์‹์œผ๋กœ ๋๊นŒ์ง€ ๊ฐ„ ํ›„, ํ•˜๋‚˜์”ฉ ์˜ฌ๋ฆฌ๋ฉด์„œ ๊ฐ€์žฅ ํฐ ๊ฑธ ๋ฐ˜ํ™˜
  • 0โ‡ i < j โ‡ M ์ผ๋•Œ, array[i] 0 ์ด๊ณ , j M์ด๋ฉด ๋ฐ”๊พธ์ง€ ์•Š์Œ.
  • 10 ์ดํ•˜๋Š” ๋ฌด์กฐ๊ฑด -1, ๋‚˜๋จธ์ง€๋Š” 0์ด ๋ฐ˜ํ™˜๋˜๋ฉด ํ•œ๋ฒˆ๋„ ๋๊นŒ์ง€ ๋„๋‹ฌํ•˜์ง€ ๋ชปํ•œ ๊ฒƒ์ด๋ฏ€๋กœ K๋ฒˆ ๋ฐ”๊พธ๊ธฐ ์—ฐ์‚ฐ์ด ๋ถˆ๊ฐ€๋Šฅํ•œ ๊ฒƒ. ์ฆ‰, -1 ์ถœ๋ ฅ

์ฝ”๋“œ

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int N, K, length, inputArray[7];
int dp[1000001][11];
 
void nIntoArray(int n, int* a);
int arrayIntoN(int* a);
int dynamic(int deep);
void swap(int* a, int* b);
 
int main() {
	cin >> N >> K;
 
	int index = 7;
	for (int i = 1000000; i >= 1; i /= 10) {
		if (N >= i) {
			length = index;
			break;
		}
		index--;
	}
 
	nIntoArray(N, inputArray);
	if (N < 10)
		cout << -1;
	else {
		int ans = dynamic(0);
		if (ans == 0)
			cout << -1;
		else
			cout << ans;
	}
}
 
void nIntoArray(int n, int* a) {
	for (int i = 0; i < length; i++) {
		a[i] = n % 10;
		n /= 10;
	}
}
int dynamic(int deep) {
	int num = arrayIntoN(inputArray);
	if (deep == K)
		return num;
	if (dp[num][deep] != 0)
		return dp[num][deep];
 
	int ans = 0;
	for (int i = 0; i < length-1; i++) {
		for (int j = i+1; j < length; j++) {
			if (inputArray[i] != 0 || j != length - 1) {
				swap(&inputArray[i], &inputArray[j]);
				ans = max(dynamic(deep + 1), ans);
				swap(&inputArray[j], &inputArray[i]);
			}
		}
	}
	dp[num][deep] = ans;
	return ans;
}
 
void swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
 
int arrayIntoN(int* a) {
	int result = 0, multi = 1;
	for (int i = 0; i < length; i++) {
		result += a[i] * multi;
		multi *= 10;
	}
	return result;
}