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

문제

---

 

문제 풀어보기

 

 

풀이

---

 

재귀를 돌면서 모든 경우를 탐색하는 것은

굉장히 기본적인 완전 탐색 방법입니다.

 

 

 

하지만 이상하게 교환횟수가 7개 정도만 넘어가면

계속해서 시간초과가 뜨더군요.

 

 

 

생각해봅시다.

주어지는 수는 최대 6자리의 숫자입니다.

여기서 두개의 인수를 교환해서 원하는 숫자를 얻기 위해서는

최대 몇번의 교환이 필요할까요?

 

 

 

카드게임을 예를 들어 봅시다.

도둑잡기, 원카드, 훌라 어떤 게임이든 상관없이

손에 6장의 카드가 있습니다.

 

 

 

우리는 이 카드를 정리하기 위해

한 카드 씩 원하는 위치에 가져다 놓습니다.

이 과정은 두 개의 위치를 교한 하는 것과 크게 다르지 않습니다.

 

 

 

그리고 우리는 정확히 카드의 개수만큼 교환할 수 있다면

어떤 순서의 배열이든 만들 수 있습니다.

 

 

 

그렇기 때문에 이 문제에서도

재귀를 돌 때 교환 횟수가 아무리 많이 주어져도

카드 수만큼만 교환해주면 답을 찾을 수 있습니다.

코드

---

#include <iostream>
#include <vector>
#include <string>

using namespace std;
int n;
int ans;

void ok(int cnt, string s, int a) {
	if (cnt == n) {
		int temp = stoi(s);
		if (temp > ans) ans = temp;
		return;
	}

	int sz = s.size();
	for (int i = a; i < sz-1; i++) {
		for (int j = i + 1; j < sz; j++) {
			char temp = s[i];
			s[i] = s[j];
			s[j] = temp;
			ok(cnt + 1, s, i);
			temp = s[i];
			s[i] = s[j];
			s[j] = temp;
		}
	}

}



int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int T;
	cin >> T;

	for(int t =1; t <=T; t++){
		string s;
		cin >> s >> n;
		ans = 0;
		if (n > s.size()) 	n = s.size();

		ok(0, s, 0);

		cout << "#" << t << ' ';
		cout << ans << '\n';

	}

	return 0;
}