[SWEA_D3] 1244번 - 최대 상금

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE

SW Expert Academy

조건이 붙은 완전탐색 문제다.

dfs 알고리즘으로 풀 수 있다.

단, 단순히 뒤의 숫자가 앞의 숫자보다 같거나 큰 경우에 대해서 진행한다면 시간초과가 난다.

바꾼 뒤에 기준이 되는 베이스 포인트를 넘겨주고 2중 for문의 바깥 루프에서 이 값부터 기준으로 삼아 탐색을 하면 시간초과가 나지 않고 풀 수 있다.

 

아래는 전체 코드.

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string num;
int answer, MaxChg;
void dfs(int idx, int change){
    if (change == MaxChg){
        answer = max(answer, stoi(num));
        return;
    }
    for (int i = idx; i < num.length(); i++){
        for (int j = i + 1; j < num.length(); j++){
            if (num[j] >= num[i]){
                swap(num[i], num[j]);
                dfs(i, change + 1);
                swap(num[i], num[j]);
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc;
    cin >> tc;
    for (int T = 1; T <= tc; T++){
        cin >> num >> MaxChg;
        answer = 0;
        dfs(0, 0);
        cout << "#" << T << " " << answer << '\n';
    }
    return 0;
}