[BOJ 2505 // C++] 두 번 뒤집기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2505번 문제인 두 번 뒤집기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/2505 

2505번: 두 번 뒤집기

2561번 문제에서 뒤집는 횟수가 줄어들고 N이 약간 커진 문제이다. 2561번과 같은 방식으로 풀 수 있으므로 풀이는 해당 글을 참고하자.

 

입력의 크기가 충분히 작으므로, 위와 같은 방법을 사용하지 않고도 뒤집어서 "인접한 원소의 차가 1을 넘는 쌍"의 개수가 감소하는 가능한 모든 구간을 O(N^2)으로 탐색해 두번 뒤집는 것을 시도하는 것으로도 문제를 해결할 수 있을 것이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int N;
int arr[10002];
vector<pair<int, int>> ans;

bool solve(int t) {
	vector<int> gap; // idx와 idx+1번째 arr값이 1보다 차이가 크다
	for (int i = 0; i <= N; i++) {
		if (abs(arr[i + 1] - arr[i]) > 1) gap.emplace_back(i);
	}

	int gsize = gap.size();
	if (gsize > t * 2) return 0;
	if (gsize == 0) return 1;

	for (int i = 0; i < gsize; i++) {
		for (int j = i + 1; j < gsize; j++) {
			int L = gap[i] + 1, R = gap[j];
			for (int LL = L, RR = R; LL < RR; LL++, RR--) {
				swap(arr[LL], arr[RR]);
			}
			if (solve(t - 1)) {
				ans.emplace_back(make_pair(L, R));
				return 1;
			}
			for (int LL = L, RR = R; LL < RR; LL++, RR--) {
				swap(arr[LL], arr[RR]);
			}
		}

		int idx = gap[i]; int val = arr[idx];
		for (int k = 1; k < idx; k++) {
			if (abs(arr[k] - val) == 1) {
				for (int LL = k, RR = idx - 1; LL < RR; LL++, RR--) {
					swap(arr[LL], arr[RR]);
				}
				if (solve(t - 1)) {
					ans.emplace_back(make_pair(k, idx - 1));
					return 1;
				}
				for (int LL = k, RR = idx - 1; LL < RR; LL++, RR--) {
					swap(arr[LL], arr[RR]);
				}
				
				for (int LL = k + 1, RR = idx; LL < RR; LL++, RR--) {
					swap(arr[LL], arr[RR]);
				}
				if (solve(t - 1)) {
					ans.emplace_back(make_pair(k + 1, idx));
					return 1;
				}
				for (int LL = k + 1, RR = idx; LL < RR; LL++, RR--) {
					swap(arr[LL], arr[RR]);
				}
			}
		}

		for (int k = idx + 1; k <= N; k++) {
			if (abs(arr[k] - val) == 1) {
				for (int LL = idx, RR = k - 1; LL < RR; LL++, RR--) {
					swap(arr[LL], arr[RR]);
				}
				if (solve(t - 1)) {
					ans.emplace_back(make_pair(idx, k - 1));
					return 1;
				}
				for (int LL = idx, RR = k - 1; LL < RR; LL++, RR--) {
					swap(arr[LL], arr[RR]);
				}

				for (int LL = idx + 1, RR = k; LL < RR; LL++, RR--) {
					swap(arr[LL], arr[RR]);
				}
				if (solve(t - 1)) {
					ans.emplace_back(make_pair(idx + 1, k));
					return 1;
				}
				for (int LL = idx + 1, RR = k; LL < RR; LL++, RR--) {
					swap(arr[LL], arr[RR]);
				}
			}
		}
	}

	return 0;
}

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

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];
	arr[N + 1] = N + 1;

	solve(2);

	while (ans.size() < 2) ans.emplace_back(make_pair(1, 1));

	while (!ans.empty()) {
		cout << ans.back().first << ' ' << ans.back().second << '\n';
		ans.pop_back();
	}
}