[SW Expert Academy] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금 (C++)

1244 SW Expert Academy [S/W 문제해결 응용] 2일차 - 최대 상금

🗄 문제

문제의 경우 무단 복제를 금지한다고 작성되어 있으므로 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 인지 고민했는데 완전탐색 인 것을 보고 알고리즘 공부를 다시해야할 것 같다고 생각했다.