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

https://swexpertacademy.com/main/main.do

SW Expert Academy

1. 해결방법

처음에는 for문을 이용해서 횟수만큼 가장 0번째값과 가장 큰 값을 교환, 이후 1번째 값과 가장 큰 값을 교환 .... 하는 방식으로 해결하려 했으나 배열의 수보다 회전의 수가 많아지거나 같은 자리가 교환 되어버리는 문제가 생겼다 따라서 dfs를 사용하여 모든 경우의 수를 비교하는 방법으로 해결하였다.

---

2. 코드

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

int total;
int num = 0;
string tmp;
int result;
void dfs(int x, int dept) {
	if (dept == num) {
		if (result < stoi(tmp)) {
			result = stoi(tmp);
		}
		return;
	}
	else {
		for (int i = x; i < tmp.size(); i++) {
			for (int j = i; j < tmp.size(); j++) {
				if (i == j) continue;
				if (tmp[i] <= tmp[j]) {
					swap(tmp[i], tmp[j]);
					dfs(i, dept + 1);
					swap(tmp[i], tmp[j]);
				}
			}
		}
	}
}
int main()
{
	cin >> total;
	for (int i = 0; i < total; i++) {
		result = 0;
		cin>> tmp;
		scanf("%d", &num);
		result = stoi(tmp);
		dfs(0, 0);
		printf("#%d %d\n", i + 1, result);
	}
}

---

3. 주의사항

같은 자리가 서로 바뀌는 것을 방지하기 위해 if (i == j) continue; 부분이 꼭 필요하다.