[C++] SWEA 1244 - 최대 상금

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE&&&

SW Expert Academy

<풀이>

1. 교환 횟수가 될 때 까지, 각 자리 숫자를 모두 교환해본다.

2. 교환된 최댓값을 갱신하고, 출력한다.

 

<해법>

1.  교환횟수가 많아질 경우, 시간초과 해결 방법

=> 백트래킹을 이용하여 숫자를 모두 교환하는 방식까지는 쉽게 생각할 수 있습니다. 하지만, 교환횟수가 많아지면 시간초과가 나옵니다. 여기서, 다른 방식으로 문제에 접근해야 겠다는 생각을 할 수 있습니다.

 

샘플 input인 456789, 10 으로 알아보겠습니다.

정답은 987645 입니다. 뒤 두 숫자가 45입니다.

이 말은 많은 반복을 하였음에도 불구하고, 최댓값이 아닐 수 있다 를 의미합니다. 그리고, 987654에서 교환 횟수를 맞추기 위해 987645로 교환을 했다는 것으로 생각할 수 있습니다.

만약 11번 교환할 경우 987654가 되고, 12번 교환할 경우 987645, 13번 987654 ... 이런 식으로 계속 나아갈 것이라고 유추할 수 있습니다.

 

그렇다면 여기서 중요한 것은 '최댓값을 만드는 동전의 최소교환횟수' 라고 생각할 수 있습니다.

그 횟수를 넘어설 경우, 뒤에 두 숫자만 바꾸어서 교환을 진행할 것이기 때문입니다.

 

다시, 위 샘플 input을 풀어보도록 하겠습니다.

456789는 3번의 교환만에 987654(최댓값)을 만들 수 있습니다. 

이후 4번 교환시 987645, 5번 987654, 6번 987645 ... 이렇게 진행됩니다.

 

다른 예시로 풀어보겠습니다. 12345 5 입니다.

12345는 2번의 교환만에 54321을 만들 수 있습니다.

이후 3번 54312, 4번 54321, 5번 54312 이므로 정답은 54312 입니다.

 

규칙이 보이실 거라고 생각합니다.

---

저의 풀이 방식이었습니다. 더 길게 쓰면 어차피 안보실 것 같아서 쓰지 않았습니다.

위 문제는 테스트 케이스가 몇 개 없어서 정확한 정답이 아닌데도 정답을 맞을 수 있습니다. 

예제 테스트 케이스를 몇개 만들어 보았습니다.

 

//input

14

49 1

49 2

49 3

12345 1

12345 2

12345 3

12345 4

12345 5

456789 1

456789 2

456789 3

456789 4

456789 5

456789 6

 

//output

#1 94
#2 49
#3 94
#4 52341
#5 54321
#6 54312
#7 54321
#8 54312
#9 956784
#10 986754
#11 987654
#12 987645
#13 987654
#14 987645

 

input을 반대로 해보셔도 도움이 될 것 같습니다.(49 -> 94, 12345 -> 54321)

 

#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
string s;
int change;
 
//최대 s
string maxS;
 
//maxS를 만들 수 있는 최소교환횟수
int minChangeCnt;
 
//바뀐 change 값
int changeCnt;
 
//정답값
string answer;
 
//문자열 바꾸기
void swap(string& str, int x, int y) {
    char tmp = str[x];
    str[x] = str[y];
    str[y] = tmp;
}
 
//완전탐색(각 자리에서 다른 자리와 교환 or 교환X)
void go(int index, int cnt) {
 
    //모든 자리마다 탐색이 끝난 경우 : 종료
    if (index > s.length()) {
        return;
    }
 
    //maxS를 찾아 낼 경우 : 교환 최소 횟수 갱신
    if (s == maxS) {
        if (minChangeCnt == -1 || cnt < minChangeCnt) {
            minChangeCnt = cnt;
        }
    }
 
    //교환 횟수를 채운 경우 : 최대값 갱신 후 종료
    if (cnt == changeCnt) {
        if (answer == "" || stoi(s) > stoi(answer)) {
            answer = s;
        }
        return;
    }
 
    //각 자리마다 바꾸기
    for (int i = 0; i < s.length(); i++) {
        if (i == index) {
            go(index + 1, cnt);
        }
        else {
            swap(s, index, i);
            go(index + 1, cnt + 1);
            swap(s, i, index);
        }
    }
}
 
//문자열에 같은 숫자가 있는지 없는지 판단
bool hasSame(string str) {
    for (int i = 0; i < str.length() - 1; i++) {
        char check = str[i];
        for (int j = i + 1; j < str.length(); j++) {
            if (check == str[j]) {
                return true;
            }
        }
    }
    return false;
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        answer = "";
        maxS = "";
        minChangeCnt = -1;
        changeCnt = 0;
 
        //입력
        cin >> s >> change;
 
        //maxS : s로 만들 수 있는 최대값(s:12345 -> maxS:54321)
        maxS = s;
        sort(maxS.begin(), maxS.end(), greater<char>());
 
        //교환 횟수 줄이기(최소 문자열 길이만큼만 바꿔도 최댓값을 만들 수 있으므로)
        changeCnt = change > s.length() ? s.length() : change;
 
        //탐색
        go(0, 0);
 
        //교환 횟수 안에 최댓값을 만들 수 있다면
        if (minChangeCnt != -1) {
            answer = maxS;
 
            //s에 같은 숫자가 있는 경우, 같은 숫자끼리 무한 반복 -> 최댓값 유지
            //s에 같은 숫자가 없는 경우, 뒤에 두 숫자를 바꿀지 말지 결정
            if (!hasSame(s)) {
                //(교환횟수 - 최댓값을 만들 수 있는 최소교환횟수)가 홀수일 경우 뒤 두 숫자 교환
                if ((change - minChangeCnt) % 2 == 1) {
                    swap(answer, answer.length() - 2, answer.length() - 1);
                }
            }
        }
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

백트래킹에 대해 알아볼 수 있는 문제였습니다.