최대 상금

최대 상금

완전탐색으로 풀면 된다.

#include <stdio.h>
 
int t, n, m, len, max_val;
int a[7];
int check[1000000];
 
void clear_check(){
    for (int i = 0; i < 1000000; i++){
        check[i] = 0;
    }
}
 
int pow(int n, int k){
    if (k == 0) return 1;
    return n*pow(n, k - 1);
}
 
int max(int a, int b){
    return (a > b) ? a : b;
}
 
int min(int a, int b){
    return (a < b) ? a : b;
}
 
void Swap(int x, int y){
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}
 
int calc(){
    int ans = 0;
    for (int i = 0; i < len; i++){
        ans += (a[i] * pow(10, len - i - 1));
    }
    return ans;
}
 
void solve(int cnt, int x, int y){
    int calc_val = calc();
    if (check[calc_val] == 0 || check[calc_val] > cnt){
        check[calc_val] = cnt;
        if (cnt == m){
            max_val = max(max_val, calc());
        }
        else{
            for (int i = 0; i < len; i++){
                for (int j = 0; j < len; j++){
                    if (i == j) continue;
                    Swap(i, j);
                    solve(cnt + 1, i, j);
                    Swap(i, j);
                }
            }
        }
    }
    else{
        if ((m - cnt) % 2 == 0){
            max_val = max(max_val, calc_val);
        }
        else {
            bool flag = false;
 
            for (int i = 0; i < len - 1; i++){
                if (a[i] < a[len - 1]){
                    flag = true;
                    Swap(i, len - 1);
                    max_val = max(max_val, calc());
                    Swap(i, len - 1);
                    break;
                }
            }
            if (!flag){
                Swap(len - 2, len - 1);
                max_val = max(max_val, calc());
                Swap(len - 2, len - 1);
            }
        }
    }
}
 
int main(){
    scanf("%d", &t);
 
    for (int tc = 1; tc <= t; tc++){
        scanf("%d %d", &n, &m);
 
        max_val = 0;
        clear_check();
 
        //입력받은 n 길이 구하기
        len = 5;
 
        while (true){
            if (pow(10, len) <= n){
                break;
            }
            len--;
        }
        ++len;
        
        //a[i]에 저장
        for (int i = 0; i < len; i++){
            a[i] = (n / pow(10, len - i - 1))%10;
        }
 
        for (int i = 0; i < len; i++){
            for (int j = 0; j < len; j++){
                if (i == j) continue;
                Swap(i, j);
                solve(1, i, j);
                Swap(i, j);
            }
        }
 
            
        printf("#%d %d\n", tc, max_val);
    }
 
}