[SWEA] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금 d3 (c++)

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

d2만 풀다가 d3푸니까 너무 어려웠다 ㅠㅠ 어떻게 풀어야할지 한참 걸렸는데..

DFS로 풀어보자! 하고 겨우 푸니까 시간초과가 났다. 

https://eunchanee.tistory.com/149

이분의 블로그를 참고해서 문제를 제대로 안읽었다는걸 알았다..

 

숫자판의 정보는 정수형 숫자로 주어지고 최대 자릿수는 6자리이며, 최대 교환 횟수는 10번이다.

 

자릿수보다 교환횟수가 더 큰경우가 있는데, 사실 자릿수보다 교환횟수가 커지면

if( cnt == n )  가 성립되기 위해서는 재귀호출이 계속 반복되기때문에 시간초과가 날 수 밖에 없다 ㅠㅠ

(이미 DFS를 실행한 수에 대해서도 또 DFS를 실행하게 됨)

 

그래서 만약 교환횟수가 자릿수보다 클 경우,

if(n > s.length()) n = s.length() - 1; 

이렇게 해줘야 시간초과가 나지 않는다.

 

잘 이해가 안돼서 아래처럼 그려가면서 풀었다.

 

---

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

string s;
int n;
int Max = 0;

void DFS(int V, int cnt){
    if( cnt == n ) { Max = max(Max, stoi(s));  return; }
    
    for(int i=V;i<s.length()-1;i++){
        for(int j=i+1;j<s.length();j++){
            
            swap(s[i], s[j]);
            DFS(i, cnt+1);
            swap(s[j], s[i]); //원래대로 복귀
            
        }
    }
}

int main() {

    int T;
    cin >> T;
    for(int t=1; t<=T; t++) {
        Max = 0;
        cin >> s >> n;
        if(n > s.length()) n = s.length() - 1;
        DFS(0, 0);
        
        
        cout << "#" << t << " " << Max << "\n";
    }
    
    return 0;
}