SW Expert Academy - 1244. 최대 상금

문제링크

• 최대상금

문제설명

• 최대 6개의 숫자판이 주어진다.
• 각 숫자판에는 0~9가 적혀있고 만약 8,8,8,3,2 의 순서라면 88832 원의 보너스 상금을 획득한다.
• 카드는 동일한 위치의 중복 교환도 허용하며 카드를 교환해야 하는 횟수가 주어진다.
  • 반드시 그 횟수만큼 교환해야 한다.
• 정해진 횟수만큼 숫자판을 교환했을 때 받을 수 있는 가장 큰 금액을 구하라

문제접근1

• 처음에는 내림차순으로 정렬하는 과정 중 일부라고 생각했다. 그래서, 교환하다가 내림차순으로 정렬이 된다면 일의자리와 십의자리에 위치한 두 숫자만 계속 교환하도록 했다.
• 그러나, 이 방법은 동일한 위치의 중복을 허용하는 교환 조건에서 마주할 수 있는 다양한 이슈에 대해서 유연하게 대응하지는 못했다.
  • 같은 숫자가 있는 경우 그 두개의 숫자만 계속 교환해주어야 내림차순을 그대로 유지할 수 있다.
  • 내림차순을 먼저 찾은 후에 교환을 하는 것이 과연 최대가 되는 방법일까?? 앞에서 숫자판을 충분히 교환한 후 마지막에 내림차순이 되도록 맞춰서 교환하는 방법도 있지 않을까??
• 위와 같은 이유들로 테스트케이스가 한 두개씩 틀리게 되면서 다른 로직을 생각해야 했다.

문제접근2

• 무조건 주어진 횟수만큼 교환했을 때만 재귀호출을 빠져나오도록 구현한다.
• 숫자판 교환은 동일한 위치에서의 교환도 허용하므로 교환할 카드를 선택할 때 본인을 제외한 모든 카드를 선택할 수 있도록 한다.
• 시간 초과를 막기 위해 이미 나왔던 결과에 대해서는 재귀호출을 진행하지 않는다.

구현

#include <iostream>
#include <string>
#include <vector>
#include <memory.h>
#include <algorithm>
using namespace std;

string numStr;
int ans = 0;
vector<int> cand[11];

void getMaxNumber(int cnt, int changeCnt) {
	int val = stoi(numStr);
	if (cnt == changeCnt) {
		ans = max(ans, val);
		return;
	}

	for (int i = 0; i < cand[cnt].size(); i++) {
		if (cand[cnt][i] == val)
			return;
	}

	cand[cnt].push_back(val);

	for (int i = 0; i < numStr.size()-1; i++) {
		char num1 = numStr[i];
		for (int j = i + 1; j < numStr.size(); j++) {
			char num2 = numStr[j];
			numStr[i] = num2;
			numStr[j] = num1;
			getMaxNumber(cnt + 1, changeCnt);
			numStr[i] = num1;
			numStr[j] = num2;
		}
	}
}
int main(int argc, char** argv)
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int test_case;
	int T;
	// freopen("input.txt", "r", stdin);
	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		int changeCnt;
		cin >> numStr >> changeCnt;
		ans = 0;
		
		for (int cnt = 0; cnt < changeCnt; cnt++) {
			cand[cnt].clear();
		}
		getMaxNumber(0, changeCnt);
		cout << "#" << test_case << " " << ans << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}