[SWEA/C++] 1244: 최대 상금

✅ D3

✏️ 1차 솔루션

⭐️ DFS

1. 모든 인덱스를 돌면서 현재 위치 다음 숫자 중에 현재 숫자보다 같거나 큰 숫자 있으면 교환
2. 바꾼 숫자에 대해 처음부터 다시 탐색

🚨 1차 trouble

백트래킹을 사용한다고 시도했으나 결국 엄청난 다중 for문을 사용하게 되어 시간초과 발생..

✏️ 최종 솔루션

⭐️ 백트래킹

1. 만약 입력 받은 숫자 자리보다 교환 횟수가 더 크다면 교환 횟수를 주어진 숫자 자리수로 줄여줌
   ➡️ 숫자 자리수만큼 바꾼 이후에는 같은 자리 반복해서 바꾸는 것밖에 되지 않기 때문에 불필요한 연산을 생략해서 시간초과 방지 목적
2. 0번 인덱스부터 탐색 시작
   1) 교환한 횟수를 갱신하면서 탐색 ➡️ 교환 횟수 채우면 최대값 갱신하고 return
   2) 현재 인덱스를 계속 갱신해주면서 갱신한 인덱스 숫자보다 뒤에 있는 숫자가 크다면 갱신한 인덱스와 교환하고 현재 인덱스, 교환 횟수 +1 dfs
   ❗️ 이때 현재 인덱스는 문자열 크기 -2 자리까지만 갱신 가능 ➡️ 더 이상 갱신할 뒷 자리가 없기 때문

📌 self feedback

1. 숫자를 바꿀 때마다 처음부터 다시 탐색하는 것이 아니라 바꾼 자리 이후부터 교환 가능한 것이 있는지 탐색하는 것이 관건
   ➡️ 현재 자리로 더 큰 수를 교환할 수 있다고 하더라도 그 작업은 백트래킹한 이후에 갱신할 수 있으므로 다시 전체 범위를 탐색할 필요는 없음
2. 문자열에서 문자를 교환할 때 swap 함수 사용하면 간편하게 바꿀 수 있음

✏️ 최종 code

#include<iostream>
#include <algorithm>
#include <string>

using namespace std;

int mx,c;
string s;
void dfs(int idx, int cnt) {
    if(cnt==c) {
        mx=max(stoi(s),mx);
        return;
    }
    
    for(int i=idx;i<s.size()-1;i++) {
        for(int j=i+1;j<s.size();j++) {
            swap(s[i],s[j]);
            dfs(i,cnt+1);
            swap(s[i],s[j]);
        }
    }
}

int main()
{
    int t;
    cin >> t;
    for(int i=1;i<=t;i++) {

        cin >> s >> c;

        mx=-1;
        if(c>s.size()) c=s.size();
        dfs(0,0);
        
        cout << '#'<<i<<" " << mx<< '\n';
    }
    
    return 0;
}