[C++] 삼성 1244. [S/W 문제해결 응용] 2일차 - 최대 상금

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
int max_number;
int number_check[10] = {0, };
 
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}
 
void quiz(vector<int> price, int change, int index) {
    if (change == 0) {
        int number = 0;
        int mul = 1;
        for (int i = price.size() - 1; i >= 0; i--) {
            number += price[i] * mul;
            mul *= 10;
        }
        if (max_number < number)
            max_number = number;
        return;
    }
 
    if (index == price.size() - 1) {
        if (change % 2 == 0) {
            quiz(price, 0, index);
        }
        else {
            for (int i = 0; i < 10; i++) {
                if (number_check[i] >= 2) {
                    quiz(price, 0, index);
                    return;
                }
            }
            swap(price[index - 1], price[index]);
            quiz(price, 0, index);
        }
        return;
 
    }
 
    int max_num = 0;
    for (int i = index + 1; i < price.size(); i++) {
        if (max_num < price[i]) {
            max_num = price[i];
        }
    }
 
    if (price[index] < max_num) {
        for (int i = index + 1; i < price.size(); i++) {
            if (max_num == price[i]) {
                swap(price[index], price[i]);
                quiz(price, change - 1, index + 1);
                swap(price[index], price[i]);
            }
        }
    }
    else quiz(price, change, index + 1);
 
}
 
int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int input, change;
        max_number = 0;
        vector<int> price;
        cin >> input >> change;
        while (input != 0) {
            int element = input % 10;
            price.push_back(element);
            number_check[element]++;
            input = input / 10;
        }
        reverse(price.begin(), price.end());
        quiz(price, change, 0);
 
        cout << "#" << t << " " << max_number << endl;
        memset(number_check, 0, 10);
    }
 
 
    return 0;
}