취미로 코딩하기

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

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

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

주어진 배열을 정렬시키기 위해 다음 순서로 뒤집어야할 구간의 후보는 다음과 같다.

1) i-1번째 원소와 i번째 원소의 차가 1보다 크고, j번째 원소와 j+1번째 원소의 차가 1보다 큰, i<j를 만족하는 구간 [i, j]

2) i-1번째 원소와 i번째 원소의 차가 1보다 크고, i번째 원소와 j+1번째 원소의 차가 1인, i<j를 만족하는 구간 [i, j]

3) i-1번째 원소와 j번째 원소의 차가 1이고, j번째 원소와 j+1번째 원소의 차가 1보다 큰, i<j를 만족하는 구간 [i, j]

위와 같은 구간들을 뒤집어가며 3회 안에 배열이 정렬이 되는지를 백트래킹을 통해 구해내자.

2)와 3)의 경우를 살펴야하는 이유가 바로 와닿지 않는다면 아래와 같은 입력 예시를 잘 생각해보자:

8
3 4 1 2 5 7 6 8

주어진 배열의 맨 앞에 0, 맨 마지막에 N+1을 삽입해 복잡한 보더케이스 구현을 피하자.

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

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

int N;
int arr[1002];
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(3);

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

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