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

[SW Expert Academy, Level 3, c++]

문제를 보자마자 처음 한 생각은 "일단 무식하게 모든 경우의 수를 다 구해보자" 였다.
교환 -> 재귀 -> 교환 되돌리기

이 문제에서 까다로웠던 점은 교환 횟수를 무조건 다 채워야 한다는 점이였다.
기저 사례에서 해당 부분을 처리해 주었다.

최적화할 부분이 있었는데, 완전 탐색을 할 때, a 와 b 를 바꾼 다고 할 때, a > b 라면 해당 재귀는 아예 시도하지 않아도 된다는 점이다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
 
// 중복된 수가 있는가
bool is_true = false;
 
// 주어진 수 n 에 대하여 trade 번 교환 했을 때 가장 큰 수를 반환.
int get_num(int n, int step, int trade) {
    string s = to_string(n);
 
    // 기저 사례
    if (s.size() == 1) { // 1. 주어진 수의 길이가 1일 경우
        return n;
    }
    if (trade == 0) { // 2. 교환을 더 이상 할 수 없을 경우
        return n;
    }
    if (step == s.size()) { // 3. 모든 교환할 수 있는 경우를 다 했을 경우
        if (trade > 0) { // 교환 할 수 있는 횟수가 아직 남았을 때
            if (is_true) // 중복된 수가 존재 할 경우 교환 가능한 횟수는 의미 없음
                return n;
            else {
                if (trade % 2 == 0) { // 짝수면 상호 교환 가능
                    return n;
                } else { // 홀수면 최대 값을 위해 마지막, 마지막 전을 바꿈
                    swap(s[s.size() - 1], s[s.size() - 2]);
                    return stoi(s);
                }
            }
        } else {
            return n;
        }
    }
    int ret = 0;
    for (int i = step; i < s.size(); i++) {
        if (s[i] < s[step]) // 애초에 step 이 더 크면 바꿀 필요가 없음
            continue;
        swap(s[step], s[i]);
        if (step == i) // 자기 자신을 교환 할 경우는 trade 가 줄어 들 지 않음
            ret = max(ret, get_num(stoi(s), step + 1, trade));
        else
            ret = max(ret, get_num(stoi(s), step + 1, trade - 1));
        swap(s[i], s[step]);
    }
    return ret;
}
 
int main() {
    int test_case;
    int T;
    cin >> T;
    /*
       여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
    */
    for (test_case = 1; test_case <= T; ++test_case) {
        cout << '#' << test_case << ' ';
        /////////////////////////////////////////////////////////////////////////////////////////////
        /*
             이 부분에 여러분의 알고리즘 구현이 들어갑니다.
         */
        /////////////////////////////////////////////////////////////////////////////////////////////
        int n;
        cin >> n;
        int trade;
        cin >> trade;
        string s = to_string(n);
        is_true = false;
        for (int i = 0; i < s.size(); ++i) {
            for (int j = i + 1; j < s.size(); ++j) {
                if (s[i] == s[j])
                    is_true = true;
                break;
            }
            if (is_true)
                break;
        }
        cout << get_num(n, 0, trade) << endl;
    }
    return 0;
}

출처 : 1244 (opens in a new tab)

SW Expert Academy About Nextra