[SW Expert Academy] D3 1244. 최대 상금

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

int answer = -1;

void dfs(string res, int ch) {
	if (is_sorted(res.rbegin(), res.rend())) {
		string u_res(res);
		auto it = unique(u_res.begin(), u_res.end());

		if (ch % 2 == 0 || distance(u_res.begin(), it) < res.length()) {
			answer = stoi(res);
			return;
		}
		else {
			char temp = res[res.length() - 1];
			res[res.length() - 1] = res[res.length() - 2];
			res[res.length() - 2] = temp;
			answer = stoi(res);
			return;
		}
	}

	for (int i = 0; i < res.length(); i++) {
		char temp = res[i];
		auto iter = max_element(res.begin() + i, res.end());
		for (int j = i+1; j < res.length(); j++) {
			if (*iter > res[j]) continue;
			res[i] = res[j];
			res[j] = temp;

			if (ch - 1 == 0) {
				if (stoi(res) > answer) answer = stoi(res);
			} else if(ch - 1 >0) dfs(res, ch - 1);
			res[j] = res[i];
			res[i] = temp;
		}
	}
}

int main() {
	int tc, num, change;
	cin >> tc;

	string str;
	for (int i = 0; i < tc; i++) {
		cin >> num >> change;
		if (change == 0) {
			cout << "#" << i + 1 << " " << answer << endl;
		}
		answer = -1;
		str = to_string(num);

		dfs(str, change);

		cout << "#" << i+1 << " " << answer << endl;
	}
}

---

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

728x90

---

[접근]

DFS

.. 맞나?

https://jolly-note.tistory.com/61

[백준/baekjoon] Silver4 1388. 바닥 장식

---

[접근1]

숫자와 바꾸는 횟수를 받는다.

만약 0이면 그대로 출력 (0이 아니라는 말이 없어서 적어놨다)

answer값에 -1을 넣어주고 num을 string으로 바꿔서(#include<string> -> to_string(num)) dfs함수에 집어넣는다.

cin >> num >> change;
if (change == 0) {
    cout << "#" << i + 1 << " " << answer << endl;
}
answer = -1;
str = to_string(num);

dfs(str, change);

---

[접근2] - dfs 함수 내부1

#include<algorithm>안의 is_sorted() 함수는 기본적으로 오름차순을 확인해주는 함수이다.

내림차순인지 확인하기 위하여 rbegin(), rend()를 사용했다.

만약 이미 내림차순으로 정렬이 되어있다면, 계속 숫자를 바꿀 필요 없이 다른 작업이 필요하다.

#include<algorithm>안의 unique함수에 string을 넣어서 string의 길이가 줄어드는지 확인한다.

만약 줄어든다면 같은 숫자가 여러개 있다는 의미!! 같은 숫자끼리 계속 바꿔주면 제일 큰 숫자를 유지할 수 있다.
또한 만약 바꾸는 횟수가 짝수번 남았다면 같은걸 짝수번 바꿔주면 제일 큰 숫자를 유지할 수 있다.

따라서 내림차순으로 정렬된 숫자를 그대로 answer에 넣고 return하여 dfs함수를 끝낸다.

auto it = unique(u_res.begin(), u_res.end());

if (ch % 2 == 0 || distance(u_res.begin(), it) < res.length()) {
    answer = stoi(res);
    return;
}

---

[접근3] - dfs 함수 내부 2

접근 2와같은 상황이 아니라면 맨 마지막 두 숫자만 바꿔서 answer에 넣고 dfs함수를 끝낸다.

else {
    char temp = res[res.length() - 1];
    res[res.length() - 1] = res[res.length() - 2];
    res[res.length() - 2] = temp;
    answer = stoi(res);
    return;
}