[ SWEA 1244 ] 최대상금 (C++)

SW Expert Academy의 최대상금(1244 / d3) 문제이다.

[ 문제풀이 ]

1) 주어진 숫자에서, K번 교환했을 때의 최댓값을 찾는 문제이다. 본인은 재귀를 통한 완전탐색으로 문제를 해결했다.

   쉽게 문제를 바라본다면, 바꿀 수 있는 모든 경우를 다 바꿔보고, 교환 횟수가 되면 모든 값들을 비교해서 최댓값을 찾으면

   되는 문제이다. 하지만, 이렇게 문제를 해결할 경우 정답은 나오지만 시간초과에 걸리게 된다.

   따라서, 본인은 각 단계별로 중복체크를 하는 과정을 하나 더 넣어주었다.

   예를 들어서, "333" , 1 이 있다고 생각해보자. 주어진 숫자는 333이고, 1번 교환하는 경우 최댓값을 찾는 경우이다.

   위의 숫자를 한번 교환하게되면

   333, 333, 333 3개가 나오게 된다. 하지만, 결국 다 같은 숫자이기 때문에, 이런 경우를 중복처리를 해 주었다.

   중복처리를 하기 위해서 Visit[][] 2차원 bool형 배열을 사용하였으며,

   Visit[a][b] = true 의 의미는 "b번 교환했을 때, a라는 값은 이미 나온 값입니다." 를 의미한다.

   여기서 우리가 주의해야 할 점은, 각 단계별로 서로 다른 중복처리를 해야 된다는 것이다.

   예를 들어서, 어떤 숫자를 1번 교환했을 때, "123" 이라는 결과가 나왔다고 가정해보자. 그렇다고, 그 숫자를 2번 교환했을 때

   "123"이라는 결과가 이미 나온 결과기 때문에 못나오면 안된다는 의미이다.

   즉, 교환 횟수별로 서로 다르게 중복처리를 해줘야 한다.

   그래서 Visit[][]배열의 크기를 설정하는데 꽤 어려웠었다. 왜냐하면, 문제에서 최대 몇번까지 교환을 하는지 교환 횟수에 대한

   제한이 없기 때문이다. 그래서, 100부터 1000까지 넣어보다가 계속해서 런타임 에러.... 갑자기 숫자를 확 줄여서 10넣어보고 11

   을 넣다보니, pass를 받았다.

2) 재귀를 통해서, 바꿀 수 있는 모든 경우를 바꿔주되, 해당 교환횟수에서 나오지 않은 숫자들만 DFS로 계속해서 호출해 주었다.

   풀이 자체는 그리 어렵지 않다.

   이 풀이법은 pass를 받을 수는 있지만, 시간이 꽤 오래 걸린다. 더 빠른 방법으로는, 최댓값들을 찾아가면서, 최댓값들만

   바꿔주는 방식도 있다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
 
#define endl "\n"
#define MAX 1000000
using namespace std;
 
string Inp;
int Change_Num;
int Answer;
bool Visit[MAX][11];
 
void Initialize()
{
    Answer = 0;
    Inp.clear();
    memset(Visit, false, sizeof(Visit));
}
 
void Input()
{
    cin >> Inp;
    cin >> Change_Num;
}
 
int Invert(string S)
{
    int Sum = 0;
    for (int i = 0; i < S.length(); i++)
    {
        Sum = Sum + (S[i] - '0');
        if (i != S.length() - 1) Sum = Sum * 10;
    }
    return Sum;
}
 
void DFS(string S, int Depth)
{
    if (Depth == Change_Num)
    {
        int Inv_String = Invert(S);
        if (Inv_String > Answer) Answer = Inv_String;
 
        return;
    }
 
    for (int i = 0; i < S.length() - 1; i++)
    {
        for (int j = i + 1; j < S.length(); j++)
        {
            swap(S[i], S[j]);
            int Temp = Invert(S);
            if (Visit[Temp][Depth + 1] == false)
            {
                Visit[Temp][Depth + 1] = true;
                DFS(S, Depth + 1);
            }
            swap(S[i], S[j]);
        }
    }
}
 
void Solution()
{
    DFS(Inp, 0);
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}