[BOJ/Platinum 5] 백준 2505 두 번 뒤집기(C++)

문제 링크

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

2505번: 두 번 뒤집기

문제

1부터 N까지의 숫자가 각 칸에 차례대로 들어있는 놀이판이 있다. 예를 들어 10 칸을 가진 놀이판의 초기 상태는 다음과 같다.  

1

2

3

4

5

6

7

8

9

10

구간[i,j]는 놀이판의 왼쪽 i번째 칸부터 j번째칸 사이에 있는 모든 숫자를 말한다. 단 구간[i,j]에서 항상 i ≤ j라고 가정한다. 우리는 이 놀이판의 한 구간을 잡아서 그 구간을 완전히 뒤집을  수 있다. 만일 초기상태에서 구간[3,8]을 뒤집으면 놀이판은 다음과 같이 변한다.

1

2

8

7

6

5

4

3

9

10

이어 이 상태에서 구간[1,5]를 다시 뒤집으면 놀이판은 다음과 같이 바뀐다. 

6

7

8

2

1

5

4

3

9

10

여러분은 두 번 뒤집힌 놀이판의 상태를 입력으로 받아서 이를 다시 초기 상태로 돌리기 위해서 어떤 두 구간을 차례대로 뒤집어야 하는지를 계산해야 한다. 즉 여러분이 찾아낸 두 개의 구간대로 입력 놀이판을 차례대로 뒤집으면, 놀이판은 초기상태인 1, 2, 3, ...., N 으로 되돌아가야 한다.  

단 어떤 경우에는 초기상태로 되돌릴 수 있는 두 구간이 여러 개 있을 수도 있는데, 그러한 경우에는 그 중 하나만 출력해도 된다. 구간[i,i]를 뒤집으면 아무런 변화가 없는데 이러한 것도 허용이 된다.

입력

첫줄에는 숫자판의 크기를 나타내는 정수 N (5 ≤ N ≤ 10,000)이 주어진다. 그 다음 줄에는 두 개의 구간이 뒤집혀진 놀이판의 상태를 나타내는 숫자들이 하나의 공백을 두고 나타난다. 

출력

첫 두 줄에는 뒤집어야 할 각 구간을 차례대로 출력해야 한다. 각 줄에는 구간[i,j]를 나타내는 i와 j를 빈 칸을 사이에 두고 출력해야 한다. 입력에 대한 답은 항상 존재한다.

예제 입력 1

10
6 7 8 2 1 5 4 3 9 10

예제 출력 1

1 5
3 8

알고리즘 분류

• 구현
• 브루트포스 알고리즘

풀이

어렵진 않은 문제였다.

1~N까지의 수를 순서대로 나열한 수열을 구간을 지정해서 두 번 뒤집은 결과가 주어졌다.

이 결과를 MAP라고 하면,

1. MAP 배열의 왼쪽 또는 오른쪽부터, 순서에 맞지 않는 숫자의 처음 발견한 위치를 찾는다.(IDX1)

2. MAP 배열의 IDX1의 위치를 찾는다.(IDX2)

3. IDX1부터 IDX2까지의 구간을 뒤집는다.

4. 이걸 2번 반복한 결과가 1~N까지의 수를 순서대로 나열한 수열이 되는 경우 정답이다.

본인은 (왼쪽에서 탐색, 오른쪽에서 탐색), (왼쪽에서 탐색, 왼쪽에서 탐색), (오른쪽에서 탐색, 왼쪽에서 탐색), (오른쪽에서 탐색, 오른쪽에서 탐색)의 4가지 경우의 수를 다 따져서 두 개의 구간을 구하였다.

스페셜 저지이므로 여러 가지 답이 나올 수 있다. 뒤집는 구간이 1개밖에 없다면, (1, 1) ~ (N, N) N개의 구간 중에 아무거나 하나를 두 번째 구간으로 출력하면 되고, 본인은 (1, 1)을 출력하기로 하였다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 10005
#define LL long long
#define INF 1e9

using namespace std;
int N;
int MAP[MAX];
pair<int, int> Range[2];

void init() {
	for (int i = 0; i < 2; i++) {
		Range[i] = make_pair(0, 0);
	}
}

void DFS(int Depth, int FL, int FR, int SL, int SR, int Next[]) {
	if (Depth == 2) {
		bool Flag = true;
		for (int i = 1; i <= N; i++) {
			if (Next[i] != i) {
				Flag = false;
				break;
			}
		}
		if (Flag) {
			Range[0] = make_pair(FL, FR);
			Range[1] = make_pair(SL, SR);
		}
		return;
	}
	// 앞에서 탐색
	int IDX1 = 0;
	int IDX2 = 0;
	for (int i = 1; i <= N; i++) {
		if (Next[i] != i) {
			IDX1 = i;
			break;
		}
	}
	for (int i = 1; i <= N; i++) {
		if (Next[i] == IDX1) {
			IDX2 = i;
			break;
		}
	}
	if (Depth == 0) {
		reverse(Next + IDX1, Next + IDX2 + 1);
		DFS(Depth + 1, IDX1, IDX2, SL, SR, Next);
		reverse(Next + IDX1, Next + IDX2 + 1);
	}
	else if (Depth == 1) {
		reverse(Next + IDX1, Next + IDX2 + 1);
		DFS(Depth + 1, FL, FR, IDX1, IDX2, Next);
		reverse(Next + IDX1, Next + IDX2 + 1);
	}

	// 뒤에서 탐색
	for (int i = N; i >= 1; i--) {
		if (Next[i] != i) {
			IDX1 = i;
			break;
		}
	}
	for (int i = 1; i <= N; i++) {
		if (Next[i] == IDX1) {
			IDX2 = i;
			break;
		}
	}
	if (Depth == 0) {
		reverse(Next + IDX2, Next + IDX1 + 1);
		DFS(Depth + 1, IDX2, IDX1, SL, SR, Next);
		reverse(Next + IDX2, Next + IDX1 + 1);
	}
	else if (Depth == 1) {
		reverse(Next + IDX2, Next + IDX1 + 1);
		DFS(Depth + 1, FL, FR, IDX2, IDX1, Next);
		reverse(Next + IDX2, Next + IDX1 + 1);
	}
}

int main() {
	FIRST
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> MAP[i];
	}
	init();
	DFS(0, 0, 0, 0, 0, MAP);
	for (int i = 0; i < 2; i++) {
		if ((Range[i].first == 0) && (Range[i].second == 0)) {
			cout << 1 << " " << 1 << "\n";
		}
		else {
			cout << Range[i].first << " " << Range[i].second << "\n";
		}
	}

	return 0;
}