문제의 경우 무단 복제를 금지한다고 작성되어 있으므로 1244 번을 찾아보시면 될 것 같습니다 !
간단하게 요약하자면 다음과 같다.
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector<int> swap(vector<int> vec, int idx1, int idx2);
int getNum(vector<int> num);
void getAnswer(vector<int> num, int change, int* answer, int idx, int cnt);
int main(int argc, char** argv)
{
int test_case;
int T;
freopen("input.txt", "r", stdin);
cin >> T;
for (test_case = 1; test_case <= T; ++test_case)
{
string num;
vector<int> numVec;
int change, answer = -1;
cin >> num >> change;
for (int i = 0; i < num.length(); i++) numVec.push_back(num[i] - '0');
getAnswer(numVec, change, &answer, 0, 0);
cout << "#" << test_case << " " << answer << endl;
}
return 0;//정상종료시 반드시 0을 리턴해야합니다.
}
vector<int> swap(vector<int> vec, int idx1, int idx2) {
int tmp;
tmp = vec[idx1];
vec[idx1] = vec[idx2];
vec[idx2] = tmp;
return vec;
}
int getNum(vector<int> num) {
int answer = 0;
for (int i = 0; i < num.size(); i++) answer += pow(10, num.size() - (i + 1)) * num[i];
return answer;
}
void getAnswer(vector<int> num, int change, int *answer, int idx, int cnt) {
if (cnt == change) {
answer[0] = max(answer[0], getNum(num));
return;
}
for (int i = idx; i < num.size(); i++) {
for (int j = i + 1; j < num.size(); j++) {
if (num[i] <= num[j]) {
num = swap(num, i, j);
getAnswer(num, change, answer, i, cnt + 1);
num = swap(num, i, j);
}
}
}
if (cnt < change) {
num = swap(num, num.size() - 1, num.size() - 2);
getAnswer(num, change, answer, idx, cnt + 1);
}
}
이 문제에서 가장 중요한 포인트가 바로 교환횟수 만큼 교환해야 한다. 라는 점이다.
그냥 최댓값을 구하는 것이 아닌 것에 주의해야한다.
일단 최댓값 을 위해서는 앞으로 갈 수록 큰 수가 와야 하기 때문에, 비교할 원소의 기준 인덱스(idx
)와 그 이후의 원소 값을 비교해야 한다.
따라서 2중 loop 를 돌 때 i = idx
, j = i + 1
로 지정해 주었다.
이후 뒤의 값이 큰 경우만 swap
한 후에 (완전 탐색을 위해 추후 다시 swap
하여 제자리로 되돌려 놓음) DFS(getAnswer
) 을 진행해주었다.
이때 교환횟수 를 고려해야 하는 중요한 포인트가 생긴다.
문제에서도 다루었듯 49
로 예시를 들어보면 위의 코드의 2중 loop 만으로는 절대 풀 수 없다.
49
라는 값을 2회 교환 해야 한다고 했을때, 49
-> 94
-> . . . 와 같이 1회 교환으로 함수가 끝나버린다. 즉 이미 완전한 내림차순 으로 정렬 되어 더이상 교환할 수 없다는 점이다 !
이 부분을 어떻게 해결해야하는지를 고민한 탓에.. . . . . 오래 걸렸는데, 결과적으로는 그냥 🛑임의로 교환🛑 해버린 후에 다시 탐색을 하면 된다... ㅋ..
우리는 최댓값을 구해야 하기 때문에 최대한 아랫자리수를 교환해주면 된다.
DP
인지 Greedy
인지 고민했는데 완전탐색 인 것을 보고 알고리즘 공부를 다시해야할 것 같다고 생각했다.