[SWEA 1244] 최대 상금

문제출처

https://www.swexpertacademy.com/

문제풀이

전체탐색을 통해 풀이하였습니다. base case조건으로 교환 횟수와 현재까지 바꾼 갯수가 같으면 

지금까지의 결과와 현재 결과중 큰 값을 result에 저장했습니다.

소스코드

#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
int n, result;
string num;
void dfs(int cur, int cnt) {
    if(cnt==n) {
        result=max(result, stoi(num));
        return;
    }
    for(int i=cur; i<num.size(); i++) {
        for(int j=i+1; j<num.size(); j++) {
            if(num[i] <= num[j]) {
                swap(num[i], num[j]);
                dfs(i, cnt + 1);
                swap(num[i], num[j]);
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int tc;
    cin>>tc;
    for(int i=1; i<=tc; i++) {
        cin>>num>>n;
        result=0;
        dfs(0,0);
        cout<<"#"<<i<<" "<<result<<"\n";
    }
    return 0;
}