(SW Expert Academy) 1244. [S/W 문제해결 응용] 2일차 - 최대 상금

문제 링크

SW Expert Academy

설명은 단순했지만 생각만큼 쉽게 풀리지 않았던 문제이다.

 

첫 도전의 실패는 다음과 같다.

 

(1) 최초에는 이분 검색으로 접근을 시도했다. 하지만 예외 케이스(특히 32888의 케이스)가 쉽게 풀리지않아, 점차 코드에 예외처리가 덕지덕지 붙는게 보였고, 이분 검색은 원하는 방법이 아님을 깨달았다.

(2) 그러다가 Discussion 창에서 DFS, BFS로 풀릴 수 있다는 의견을 접해 DFS로 풀었다.

(3) DFS로 푸는것 까지는 좋았지만 예외케이스에 대한 처리는 필수적이었다 (특히 4321의 케이스)

 

문제 풀이는 다음과 같다. 

 

(1) 문자열을 숫자로 변환하여 이를 최대값과 원본값에 별도로 저장한다.

(2) DFS를 통해 비교 시작 지점과 비교 횟수를 인자로 넘겨 받는다.

(3) DFS를 통해 최대값을 판별한다. 이때 DFS진행하며 바꿨던 단어의 자리들을 원래대로 되돌리는 것 또한 잊지 않는다.

(4) 만약 DFS를 통해 최대값을 찾는데 실패한 경우(= count의 수가 줄지 않고 maxi의 값 또한 원본값과 동일하다), reverse dfs를 진행한다.

(5) reverse dfs는 말 그대로 맨 뒤에서부터 거꾸로 비교를 시작한다.

(6) 맨 뒷자리부터 비교를 시작하니 결국 값의 크고 작음 비교 없이 빠르게 비교만 하면 끝난다. 때문에 별도의 조건문 없이 자리를 바꿔준다.

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

int maxi = 0, ori = 0;
char temp;
string s = "";

void reverse(int idx, int cnt){ // 2
    if(cnt==0){
        if(stoi(s)>maxi) maxi = stoi(s);
        return;
    }
    for(int i=idx; i>=0; i--){
        for(int j=i-1; j>=0; j--){ 
                temp = s[i]; // 맨 뒤에서부터 비교하는 거라 조건따위 필요없다
                s[i] = s[j];
                s[j] =  temp;
                reverse(i,cnt-1); 
                temp = s[i];
                s[i] = s[j];
                s[j] = temp;
        }
    }
}

void dfs(int idx, int cnt){ // 1
    if(cnt==0){
        if(stoi(s)>maxi) maxi = stoi(s);
        return;
    }
    for(int i=idx; i<s.size(); i++){ 
        for(int j=i+1; j<s.size(); j++){
            if(s[i]-'0'<=s[j]-'0'){ // 주의 // 이 경우가 필요한 케이스는 77732
                temp = s[i];
                s[i] = s[j];
                s[j] =  temp;
                dfs(i,cnt-1); //제자리 바꾸기가 일어날 수 있으니 i+1이아닌 i이다
                temp = s[i];
                s[i] = s[j];
                s[j] = temp;
            }
        }
    }
    if(cnt!=0&&maxi<=ori){
        maxi = 0;
        reverse(s.size()-1, cnt);
    }
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int test_case = 0, T = 0, cnt = 0;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
        cin >> s >> cnt;
        maxi = stoi(s), ori = stoi(s);
        dfs(0,cnt);
        cout << "#" << test_case << " " << maxi << "\n";
    }
   return 0;
}