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

SWExpertAcademy의 최대상금(1244 / D3) 문제이다.

[ 문제풀이 ]
1) 이 문제에 대한 풀이 글을 예전에 한번 올렸었던 적이 있다.

   [ 최대상금 기존 풀이법 보러가기(Click) ]

   pass가 목적이라면, 기존에 풀이법을 참고해서 풀던, 지금 이글을 참고해서 풀던 상관은 없다.

   그런데, 기존의 풀이법과는 다른, 조금 더 빠르게 해결할 수 있는 방법에 대해서 소개하고자 한다.

   먼저 기존의 풀이법은 "바꿀 수 있는 모든 경우를 다 바꿔보고 최댓값을 찾는 완전탐색" 이였다.

   이번 풀이도 '완전탐색' 으로 해결을 했지만, 중간에 가지치기와 바꾸는 과정에 대한 설정을 조금 바꿔줌으로써

   훨씬 더 빠르게 해결해보고자 한다.

   먼저 전체적인 큰 방법을 설명하자면, "현재 시점으로부터 가장 큰 값을 찾아서, SWAP 하는 방식으로, 가장 큰 값들이

   숫자의 앞쪽으로 위치할 수 있도록 만들어주는 방식" 이다.

   방법만 들어보면 굉장히 간단하고 쉬울 것 같지만, 실제로 구현해보면 처리해줘야 할 요소들이 많아서 굉장히 까다로웠다.

  

   먼저 차근차근 알아보도록하자. 본인은 깊이우선탐색 방법인 DFS를 이용해서 구현해 보았는데, DFS에 호출되는

   매개변수는 2개가 있다. int Left , int Cnt.

   'Left'변수가 의미하는 것은 "현재의 시점"을 의미한다. 즉, "123"이라는 숫자를 바꿀 때, '1'은 0번째, '2'는 1번째, '3'은

   2번째 위치하게 되는데, 지금 숫자가 몇 번째 위치하고 있는지를 의미하는 것이다.

   'Cnt'변수는 지금까지 바꾼 횟수를 의미한다.

   그럼 시작해보자. 우리가 계속해서 생각해줘야 할 것은 "현재의 시점부터 모든 값들을 탐색해서, 가장 큰 값을 찾고

   그 큰 값과 Swap을 할 것이다 !" 를 생각해야 한다.

   가장 처음에는 당연히 (0, 0)으로 호출을 하게 될 것이다.

   이것이 의미하는 것은 "현재 0번째 있는 숫자에 위치하고 있고, 바꾼 횟수는 0회입니다" 이다.

   지금부터는 보다 쉬운 이해를 위해서 여러가지 예시를 들면서 설명해보겠다. 가장 먼저 이런 경우를 생각해보자.

   "123"이라는 숫자를 2번 Swap 할 때의 최대상금을 찾는 것으로 예시를 들면서 설명하겠다.

   먼저 해야할 것은 ?? "현재의 시점으로부터 최댓값 찾기 !" 이다.

   최댓값을 찾으면 '3'이 나오게 될것이다. 그럼 우리는 '1'과 '3'을 Swap 해주고 DFS를 호출하게 될 것이다.

   즉, 현재 값은 '312'가 될 것이고, DFS는 (Left + 1, Cnt + 1)로 호출됨으로써 (1, 1)로 호출될 것이다.

   그럼 이 상태에서 "현재의 시점으로부터 최댓값 찾기!" 를 진행한다면 ? '2'라는 최대값을 찾을 수 있다.

   그럼 Left와 Swap을 해준다. 즉, '312'가 '321'이 될 것이다. 2번 Swap했으니, '321'이 정답으로 나오게 된다.

   그럼 이번에는 '123'이 아닌, '321'을 2번 Swap해주는 경우를 보자.

   가장 먼저 (0, 0)으로 호출되었을 때, 최댓값을 찾으면 ? '3'이 나오게 된다.

   그런데 ! Left에 존재하는 '3'과, 찾은 최댓값 '3'은 동일한 값이기 때문에 Swap이 될 수가 없다.

   그럼 이런 경우에는 ?? 그대로 냅두는 것이다. Swap을 하지 않는다. 왜냐하면 가장 큰 숫자가 가장 앞에 올 수록

   최댓값에 가깝기 때문이다. 가장 냅둔다는 것은 ? DFS를 (Left + 1 , Cnt ) 로 호출한다는 것이다.

   저 매개변수가 의미하는 것은 "현재의 시점에서는 Swap하지 않고 그냥 넘어 가겠습니다." 를 의미한다.

   그럼 계속 진행해보자. 현재 DFS가 (1, 0)으로 호출되었지만, Swap이 일어나지 않았기 때문에 '321' 그대로 이다.

   그럼 Left = 1이고, '1번째 값으로부터 최댓값 찾기'를 하게 되더라도 마찬가지로 최댓값인 Left값과 동일하게 '2'이기

   때문에 Swap이 일어나지 않는다. 마찬가지로 그대로 DFS를 (Left + 1 , Cnt) 로 호출 !

   이제는 Left가 마지막이기 때문에 찾을 최댓값도 없다. 이 상태로 DFS 탐색이 모두 끝나버리게 될 것이다.

   우리는 Swap을 한번도 못해본 채 탐색이 끝나버렸다. 그럼 지금부터는 어떻게 해야될까 ??

   우리는 지금부터 Swap을 딱 ! 한번만 더해보거나 Swap을 하지 않아도 정답을 알아낼 수 있다.

   바로 지금까지 바꾼 횟수와, 문제에서 주어진 바꿔야 할 횟수를 비교한다면 Swap을 한번만 하거나 안해봐도 된다.

   우리는 '321'의 숫자를 2번 Swap했을 때 최대값을 구해야 한다. 하지만 우리는 DFS탐색에서 0번의 Swap을 했기 때문에

   아직 2번 Swap을 더 해봐야 한다. 하지만 ! 이 경우에는 Swap을 하지 않고 '321'이 정답이라는 것을 바로 출력해 낼 수

   있다. 어떻게 ?? 바로 '짝수번 Swap'을 해야 하기 때문이다.

   이게 무슨 소리일까 ??? 정말로 Swap을 2번 더 진행해본다고 생각해보자. 2번의 Swap을 통해서 최댓값을 얻기 위해서는

   무슨 값들끼리 Swap하는게 가장 효율적일까 ?? 정말 당연하게도, 앞 자리 숫자는 최대한 그대로 냅두는 것이 좋다.

   직관적으로 알 수 있는 것이, 가장 뒷 자리 숫자 2개를 Swap 하는 것이 가장 최대상금에 가까워 진다.

   즉, '321'에서 '3'을 그대로 냅두고, '2'와 '1'을 한번 Swap, 다시 '2'와 '1'을 한번 더 Swap 함으로써 총 2번의 Swap을

   하게되면 '321'이라는 값을 정답으로 도출해 내면 된다.

   그런데 이거 꼭 해봐야할까 ?? 어떤 숫자든, 어떤 상황에서든지 DFS 탐색 후 '짝수번 Swap을 더 해줘야 합니다' 라는

   결론이 났다면, 이는 결국 짝수번 Swap을 하더라도 지금과 같은 상황일 것이기 때문에 지금 나온 답이 정답이 된다.

   그런데 여기서 또 이해가 가지 않는 점 하나.. 왜 지금 나온 답이 정답인걸까 ??

   왜냐하면 우리는 최댓값이 앞으로 오게끔 바꿔왔기 때문이다. 이 정도만 이해하고 또 다른 예시를 한번 생각해보자.

   이번에는 '231'을 2번 Swap 하는 것으로 생각해보자.

   '2'를 기준으로 봤을 때 최댓값 '3'이 존재하므로 '2'와 '3'을 Swap해서 '321'로 (1, 1)을 호출.

   '321'에서는 더이상 최대값이 없기 때문에 (2, 1)을 호출. Left값이 마지막 숫자이기 때문에 더 이상 호출할 숫자가

   없기 때문에 그대로 종료. 우리는 '2'번 Swap을 해야하지만, '1'번만 Swap을 한 상태이다.

   아까와는 다른 상황이다. 왜 ? 아까는 Swap해야 하는 횟수가 '짝수'번 남았었다. 그런데 이번에는 ? '홀수번' 남은 상태이다.

   즉, 이 경우에는 Swap을 해줘야 한다는 것이다. 왜 ?? 결과가 달라지기 때문이다.

   '321'에서 짝수번 Swap을 해서 최댓값을 찾으면 '321'이 나오게 된다. 위에서도 말했듯이 '2'와 '1'만 계속해서 바꿔주면

   짝수번 Swap이기 때문에 결국 제자리로 돌아오기 때문이다.

   하지만 '321'에서 홀수번 Swap을 해줘야 하면 ? 똑같이 가장 뒤쪽에 위치한 숫자 2개를 바꿔준 '312'가 최댓값이 된다.

   그럼 홀수번은 직접 Swap을 해봐야 하나 ?? 아니다. 딱 한번만 Swap을 해주면 된다.

   '321'에서 1번 Swap했을 때의 최댓값은 ? '312', 3번 Swap 했을 때의 최댓값은 ? '2'와 '1'을 3번 바꿔주면 '312',

   5번 Swap해주면 ? '2'와 '1'을 5번 바꿔줬을 때 '312'. 즉, 무조건 한번만 Swap을 해주면 된다. 무슨 숫자를 ? 가장 뒤쪽에

   위치한 숫자를 !

   그리고 가장 중요한 것을 빼먹었는데 위의 과정을 위해서 우리는 DFS탐색 중간중간에서 최댓값을 저장해주는

   과정이 필요하다 !

   여기까지 정리한번 해보고 가자.

   - 우리는 최댓값이 앞쪽으로 오도록 무조건 최댓값을 찾아서 Swap을 해줄 것이다.

   - 그런데 정말 불행하게도, 이렇게 Swap해줄 경우, 문제에서 제시한 Swap횟수를 모두 못채우고 탐색이 끝나 버리는 경우가

     발생한다.

   - 이 경우에는, 남아있는 Swap횟수(문제에서 제시한 바꿔야할 횟수 - 내가 바꾼 횟수)가 짝수일 경우에는 현재 숫자가

     정답, 홀수일 경우에는 가장 마지막 숫자 2개를 1번 Swap한 것이 정답.

   - 왜 위와 같은 계산이 가능해요 ? 우리는 최댓값이 앞으로 오도록 Swap을 해줬고 중간중간 계산에서 나오는

     최댓값을 저장해 주었기 때문에 가능하다.

   이렇게 되는 것이다.

   지금까지는 남아있는 Swap횟수를 비교하면서 Swap을 더이상 하지 않거나, 한 번만 더하는 방식으로 계산을 해 주었다.

   하지만, 남아있는 Swap 횟수와 상관없이 무조건 Swap을 안할수 있는 경우도 존재한다.

   바로 "같은 숫자가 2개 이상 존재" 하는 경우이다. 같은 숫자가 2개 이상 존재한다면 ? Swap을 한번 해야 한다고 하더라도

   같은 숫자를 바꿔버리면 끝이기 때문에 Swap을 해보지 않아도 답을 알 수가 있다.

   처리해줘야할 부분이 많아서 설명도 길었고 복잡했지만 코드를 보면서 이해하지 못한 부분은 이해해보도록 하자.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define NUMBER_MAX 6
using namespace std;
 
int Number[NUMBER_MAX];                // 입력받는 숫자를 저장하기 위한 배열
int Save_Max_Number[NUMBER_MAX];    // DFS탐색 중간중간, 최댓값을 저장하는 배열
int Answer, Inp_Num, Change_Num, Len, Total_Change, Save_Max_Value;
/* Inp_Num = 입력받을 숫자 
 * Change_Num = 입력으로 받는 바꿔야 할 횟수
 * Total_Change = 내가 바꾼 횟수
 * Save_Max_Value = Save_Max_Number 배열에 저장된 숫자들을 int형으로 변환한 값.(배열형태가 아님)
*/
bool Have_Same;
/* 같은 숫자가 존재하는 숫자인지 판단하기 위한 bool형 변수. */
 
void Initialize()
{
    for (int i = 0; i < NUMBER_MAX; i++)
    {
        Number[i] = 0;
    }
    Save_Max_Value = 0;
    Answer = 0;
    Inp_Num = Change_Num = Len = 0;
    Total_Change = 0;
    Have_Same = false;
}
 
void Input()
{
    cin >> Inp_Num >> Change_Num;
}
 
void Setting_Number()
{
    /* 입력 받은 숫자에 대해서 미리 세팅 하는 함수.
     * 주어진 int형 숫자를 swap하기 위해서 배열에 옮겨주는 작업.
     * 같은 숫자가 2개이상 존재하는지 판단하는 작업.
     */
    int Idx = 6;
    int Div = 100000;
    int Num_Cnt[10] = { 0, };
 
    while (1)
    {
        if (Inp_Num / Div == 0)
        {
            Idx--;
            Div = Div / 10;
        }
        else break;
    }
 
    Len = Idx;
    Idx--;
    while (Inp_Num > 0)
    {
        int Num_Value = Inp_Num % 10;
        Number[Idx--] = Num_Value;
        Num_Cnt[Num_Value]++;
 
        if (Num_Cnt[Num_Value] >= 2) Have_Same = true;
        Inp_Num = Inp_Num / 10;
    }
}
 
void Swap(int &A, int &B)
{
    int Temp = A;
    A = B;
    B = Temp;
}
 
int Calculate(int A[])
{
    int Sum = 0;
    for (int i = 0; i < Len; i++)
    {
        Sum = Sum + A[i];
        Sum = Sum * 10;
    }
    Sum = Sum / 10;
 
    return Sum;
}
 
void DFS(int Left, int Cnt)    // (몇 번째 자리, 바꾼횟수)
{
    /* 탐색을 하는 과정. */
    int Temp = Calculate(Number);
 
    /* 중간중간 최댓값을 저장하기 위해서 기존의 값과 비교하면서 갱신
     * 이 과정이 왜 필요 ? 
       -> Swap횟수를 주어진 횟수만큼 채우지 못했을 때를 대비해서 필요.
       -> 최댓값을 만들었을 때의 Swap횟수를 판단하고, 몇 번 더 Swap해야 하는지
          판단 후, 1번만 Swap하거나 Swap안하거나를 판단하기 위해서.
     */
    if (Save_Max_Value < Temp)        
    {
        Save_Max_Value = Temp;
        Total_Change = Cnt;
        for (int i = 0; i < Len; i++) Save_Max_Number[i] = Number[i];
    }
 
    /* 정상적으로 Swap 횟수를 모두 채운 경우. */
    if (Cnt == Change_Num)
    {
        int Temp = Calculate(Number);
        if (Answer < Temp) Answer = Temp;
        return;
    }
 
    /* 현재의 시점으로부터 최댓값을 찾는 과정.*/
    int Max_Value = -987654321;
    for (int i = Left; i < Len; i++)
    {
        if (Number[i] > Max_Value)
        {
            Max_Value = Number[i];
        }
    }
 
    /* 현재의 시점으로부터의 최댓값을 찾았으니, 그 값과 Swap하는 과정. 
     * 그런데 for문이 존재하는 이유 ? 어차피 최댓값이랑만 Swap을 할건데 ??
     * 최댓값인 2개 이상인 경우가 있음.
     * 예를 들어서, Tc 2번인 2737 같은 경우, 7237로도 Swap이 가능하고, 7732로도 가능함.
       이런 경우를 대비해서 존재하는 모든 최댓값들과 모두 Swap을 해봐야하기 때문에
       for문이 필요 ! 
    */
    for (int i = Left; i < Len; i++)
    {
        if (Number[i] == Max_Value)
        {
            if (i == Left) DFS(Left + 1, Cnt);
            else
            {
                swap(Number[i], Number[Left]);
                DFS(Left + 1, Cnt + 1);
                swap(Number[i], Number[Left]);
            }
        }
    }
}
 
void Solution()
{
    Setting_Number();
    DFS(0, 0);
 
    /* 주어진 Swap횟수를 채우지 못한 경우 */
    if (Total_Change < Change_Num)
    {
        /* 1. 동일한 값이 2개이상 존재하는 숫자라면, Swap해볼 필요도 없이 정답출력. */
        if (Have_Same == true)
        {
            Answer = Save_Max_Value;
            return;
        }
        
        /* 2. 남은 Swap횟수를 판단해서, 짝수번 남았는지, 홀수번 남았는지 판단. 
         * 짝수번 남았다면, Swap을 안해봐도 최댓값이 그대로 정답.
         * 홀수번 남았다면, 가장 작은 자리 숫자 2개를 1번만 Swap 하면 그것이 정답.
         */
        int Change = Change_Num - Total_Change;
        if (Change % 2 == 0) Answer = Save_Max_Value;
        else
        {
            swap(Save_Max_Number[Len - 2], Save_Max_Number[Len - 1]);
            Answer = Calculate(Save_Max_Number);
        }
    }
}
 
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;
}