[코드업] 4684 - 자물쇠

띠 모양의 자물쇠가 있다. 이 자물쇠는 한 줄로 늘어선 N개의 칸으로 이루어져 있고, 각 칸에는 1부터 N까지의 숫자가 하나씩 들어 있다. 맨 처음에는 1번째 칸부터 N번째 칸까지 1부터 N까지 숫자가 순서대로 하나씩 들어 있다. 아래 그림 1은 10개의 칸으로 이루어진 자물쇠의 맨 처음 모양을 보여주고 있다. 

이 자물쇠를 잠그기 위해서는 다음과 같은 3회의 동작을 연속적으로 수행해야 한다. 

➀ 왼쪽으로 밀기 
➁ 구간 뒤집기 
➂ 왼쪽으로 밀기 

첫 번째 동작은 왼쪽으로 밀기이다. 칸 밖으로 밀려나간 번호는 다시 오른쪽으로 돌아온다. 그림 1의 자물쇠를 왼쪽으로 3칸 밀고 나면 그림 2와 같게 된다. 이렇게 왼쪽으로 K칸 밀기 동작을 K-왼쪽밀기라고 부른다. 이때 이다. 

그 다음 동작은 정해진 구간의 숫자를 뒤집는 것이다. 예를 들어 그림 2의 자물쇠에서 7번째 칸에서부터 9번째 칸까지 숫자 <10,1,2>를 뒤집으면 다음 그림 3과 같게 된다. P번째 칸부터 Q번째 칸까지 숫자들을 뒤집는 동작을 (P,Q)-구간뒤집기라고 한다. 이때 항상 P<Q이다. 

이 상황에서 다시 5-왼쪽밀기 동작을 수행하였다면 자물쇠 모양은 아래 그림 4와 같게 된다. 

위에서 3-왼쪽밀기, (7,9)-구간뒤집기, 다시 5-왼쪽밀기의 동작을 차례로 수행하여 자물쇠를 잠궜다. 

잠긴 자물쇠의 마지막 상태를 입력으로 받아서 그렇게 만든 3회의 동작을 찾아내는 프로그램을 작성하시오. 예를 들어 자물쇠 모양이 그림 4와 같다면 그 답은 3-왼쪽밀기, (7,9)-구간뒤집기, 5-왼쪽밀기이다.

입력

첫째 줄에 자물쇠에 있는 칸의 수를 나타내는 정수 N이 주어진다. N은 10 이상 500 이하이다. 

둘째 줄에는 잠겨 있는 자물쇠의 1번째 칸부터N 번째 칸까지 들어 있는 숫자들이 순서대로 빈칸을 사이에 두고 입력된다. 

출력

처음 K-왼쪽밀기의 를 첫째 줄에, (P,Q)-구간뒤집기의 P와 Q를 빈칸을 사이에 두고 둘째 줄에, 그리고 마지막 K-왼쪽밀기의 K를 셋째 줄에 출력한다. 만일 답이 여럿일 경우에는 그 중 하나만 출력하면 된다. 

입력 예시 

10
9 2 1 10 3 4 5 6 7 8

출력 예시

3
7 9
5

---

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;

int main(){
	int N;
	cin >> N;

	deque<int> lock(N);
	int num;
	for(int i = 0; i < N; i++)
		cin >> lock[i];

	int rotate2 = 0;
	for(int i = 0; i < N; i++){
		if(lock[N - 1] - lock[N - 2] != 1){
			lock.push_front(lock.back());
			lock.pop_back();
			rotate2++;
		}
		else break;
	}
	if(rotate2 == 0) rotate2 = N;
	// 마지막 원소 맨 앞에 넣기
	lock.push_front(lock.back());
	// 첫번째 원소를 맨 뒤에 넣기
	lock.push_back(lock[1]); // 지금 deque에 있는 총 원소수는 N + 2

	int tmp = 0;
	int endIdx = -1;
	for(int i = 1; i <= N; i++){
		if(lock[i] - lock[i - 1] != 1 && lock[i + 1] - lock[i] != 1){
			tmp++;
			endIdx = i;
		}
	}
	int startIdx = endIdx - tmp + 1;

	reverse(lock.begin() + startIdx, lock.begin() + endIdx + 1);

	int rotate1 = 0;
	for(int i = 1; i <= N; i++){
		if(lock[i] == 1){
			rotate1 = N + 1 - i;
			break;
		}
	}

	cout << rotate1 << '\n';
	cout << startIdx << ' ' << endIdx << '\n';
	cout << rotate2;

	return 0;
}