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

[문제풀기]

 1244. 최대 상금

SW Expert Academy

 

[풀이과정]

이 문제는 단순 정렬을 통해 풀수 있는 문제가 아니다.

예를 들어 12345 9 이 주어진다면, 단순 정렬을 통해서는 54321를 반환을 한다. 하지만 54321를 만드는데 

교환 횟수가 2번을 했고, 7번의 기회가 남아있기 때문에 반환을 해야되는 값은 마지막 두 자리 수가 바뀐 54312가 된다.

 

그렇기 때문에 문제를 풀기 위해서는

1. 최대값을 찾고, 그 최대값을 만들기 위해서 교환이 몇번 이뤄났는지

2. 중복 숫자가 있으면 남은 교환 횟수가 얼마인지 상관없이 최대값 반환

3. 남은 교환 횟수가 짝수인지, 홀수인지 구별

 3-1. 짝수라면 최대값이 반환

 3-2. 홀수라면 마지막 두 자리의 수를 교환 후 반환

이런 형식이 만들어진다.

 

2번의 경우

ex) 23345 값이 주어지고 최대값을 54332를 찾았으면 남의 교환의 횟수가 짝수든 홀수든 33를 교환시키면 되기 때문에 

상관없다고 한 것이다.

 

3번의 경우

중복 교환이 가능하기 때문에 남은 교환의 횟수가 짝수라면, 최대값이 정답이되고, 

홀수라면, 마지막의 두 자리의 수를 교환해줘야한다.

 

DFS() 함수를 통해 최대값을 구해주는데, 첫번째 for문을 통해 각 자리수에서 최대값을 구해준다.

그리고 두번째 for문을 통해 정렬을 해주는데, 이 때, 최대값이 중복 수가 될수 있기 때문에 for문을 사용했다.

그리고 만약 최대값이 현재 자리의 수라면 cnt로 교환 횟수는 늘리지않고, 탐색을 해주고,

최대값이 교환이 이루어졌다면, cnt+1를 통해 교환 횟수를 늘려준다.

 

[소스과정]

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
int n, ans;
string str;
int Save_Max_Value, Total_Cnt;
int Number[6];
int Save_Max_Num[6];
bool Have_Same = false;

int calculation(int a[]){
    int sum = 0;
    for(int i=0; i<str.size(); i++){
        sum += a[i];
        sum *= 10;
    }
    sum /= 10;
    return sum;
}

void DFS(int Cur, int Cnt){
    int temp = calculation(Number);

    if(Save_Max_Value < temp){
        Save_Max_Value = temp;
        Total_Cnt = Cnt;
        for(int i=0; i<str.size(); i++){
            Save_Max_Num[i] = Number[i];
        }
    }

    if(Cnt == n){
        ans = max(ans, calculation(Number));
        return;
    }

    int Max = -1;
    for(int i=Cur; i<str.size(); i++){
        Max = max(Max, Number[i]);
    }

    for(int i=Cur; i<str.size(); i++){
        if(Number[i] == Max){
            if(i == Cur) 
                DFS(Cur+1, Cnt);
            else{
                swap(Number[i], Number[Cur]);
                DFS(Cur+1, Cnt+1);
                swap(Number[i], Number[Cur]);
            }
        }
    }
}

void Setting(){
    ans = 0;
    Save_Max_Value = 0;
    Total_Cnt = 0;
    Have_Same = false;
    int Num_Cnt[10] = {0};

    int num = stoi(str);
    int size = str.size()-1;
    while(num > 0){
        int value = num % 10;
        Number[size--] = value;
        Num_Cnt[value]++;

        if(Num_Cnt[value] >= 2) 
            Have_Same = true;
        num /= 10; 
    }
}

int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);

    int T ;
    cin >> T;
    for(int test=1; test<= T; test++){
        cin >> str >> n;
        Setting();

        DFS(0, 0);

        if(Total_Cnt < n){
            if(Have_Same){
                cout << "#"<< test << " " << Save_Max_Value << "\n";
                continue;
            }

            int Change = n - Total_Cnt;
            if(Change % 2 == 0){
                ans = Save_Max_Value;
            }
            else{
                swap(Save_Max_Num[str.size()-1], Save_Max_Num[str.size()-2]);
                ans = calculation(Save_Max_Num);
            }
        }

        cout << "#"<< test << " " << ans << "\n";
    }
    

    return 0;
}

 

[해결 과정 중 실수한 부분]

 

---

이 문제는 얍문's 블로그를 참고하여 풀었다.

https://yabmoons.tistory.com/307