👓 문제 설명
퀴즈 대회에 참가해서 우승을 하게 되면 보너스 상금을 획득할 수 있는 기회를 부여받는다.
우승자는 주어진 숫자판들 중에 두 개를 선택에서 정해진 횟수만큼 서로의 자리를 위치를 교환할 수 있다.
예를 들어, 다음 그림과 3, 2, 8, 8, 8 의 5개의 숫자판들이 주어지고 교환 횟수는 2회라고 하자.
교환전> 3, 2, 8, 8, 8
처음에는 첫번째 숫자판의 3과 네 번째 숫자판의 8을 교환해서 8, 2, 8, 3, 8이 되었다.
다음으로, 두 번째 숫자판 2와 마지막에 있는 8을 교환해서 8, 8, 8, 3, 2이 되었다.
정해진 횟수만큼 교환이 끝나면 숫자판의 위치에 부여된 가중치에 의해 상금이 계산된다.
숫자판의 오른쪽 끝에서부터 1원이고 왼쪽으로 한자리씩 갈수록 10의 배수만큼 커진다.
위의 예에서와 같이 최종적으로 숫자판들이 8,8,8,3,2의 순서가 되면 88832원의 보너스 상금을 획득한다.
여기서 주의할 것은 반드시 횟수만큼 교환이 이루어져야 하고 동일한 위치의 교환이 중복되어도 된다.
다음과 같은 경우 1회의 교환 횟수가 주어졌을 때 반드시 1회 교환을 수행하므로 결과값은 49가 된다.
94의 경우 2회 교환하게 되면 원래의 94가 된다.
정해진 횟수만큼 숫자판을 교환했을 때 받을 수 있는 가장 큰 금액을 계산해보자.
🚨 접근 방법
처음에는 반복문을 이용한 브루트포스 방법을 떠올렸으나,
6개의 수가 10번 자리를 바꾼다면 1회 시행 시 6C2 = 15, 15의 10제곱이다.
시간 초과가 발생하기 때문에 DFS를 이용하며 적절한 가지치기가 필요하다고 생각했다.
조합의 개념을 빌려 현재 내가 바꾼 횟수가 바꾸어야 하는 횟수라면 탈출 조건을 만들고
0번째 인덱스부터 2개씩 비교하며 뒤에 값이 더 크다면 바꾸어 주고 dfs를 다시 들어간다.
그 후 정답에 현재 num과 비교하여 더 큰 값을 저장한다.
하지만 문제를 다시 살펴보니 4321 1이 들어온 경우 무조건 바꾸어야한다. 즉 4312가 answer에 저장이되어야한다.
따라서 마지막까지 탐색을 했는데 바꾸어야 하는 상황이 온다면 자리 값을 바꾸고 swap을 통해 answer를 갱신한다.
🚈 풀이
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string num;
int max_cnt,answer;
void dfs(int idx, int cnt) {
// 탈출 조건
if (cnt == max_cnt) {
answer = max(answer, stoi(num));
return;
}
for (int i = idx; i < num.length()-1; i++) {
for (int j = i + 1; j < num.length(); j++) {
if (num[i] <= num[j]) {
swap(num[i], num[j]);
dfs(i, cnt + 1);
swap(num[i],num[j]);
}
// 무조건 바꾸어야하는 경우
if (i == num.length() - 2 && j == num.length() - 1) {
swap(num[i], num[j]);
dfs(i, cnt + 1);
swap(num[i], num[j]);
}
}
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
cin >> T;
for (test_case = 1; test_case <= T; ++test_case)
{
cin >> num>> max_cnt;
answer = 0;
dfs(0, 0);
cout << "#" << test_case << " " << answer << "\n";
}
return 0;
}