BOJ 2478 자물쇠

사용한 알고리즘

구현

알고리즘 설명

바로 옆의 값이 1씩 차이 나지 않으면 뒤집혀진 곳이다.
이런 구간을 두 구간 찾고, 이 두 곳이 뒤집어야 하는 구간이다.
다음 왼쪽으로 밀었을 것을 생각하고 다시 찾아가기 위해서 오른쪽으로 밀어준다.
쉬프트 된 것을 생각하고 뒤집어야 하는 곳을 다시 계산한다.
쉬프트 한 뒤에 1을 찾아서 다시 오른쪽으로 미뤄준다.
결과 출력

풀이

// baekjoon 2478 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=501;

int N, arr[MAX_N], s, e;
int tmp[MAX_N];
bool visited[MAX_N];

int main() {
	scanf("%d", &N);
	for (int i=0; i<N; i++)
		scanf("%d", &arr[i]);

// 먼저 값이 1씩 차이 나지 않으면 뒤집혀진 곳이다.
	for (int i=0; i<N; i++) {
		if (arr[(N+i-1)%N]-arr[i] == 1)
			visited[(N+i-1)%N] = visited[i] = true;
		if (arr[(N+i-1)%N] == 1 && arr[i] == N)
			visited[(N+i-1)%N] = visited[i] = true;
	}
// 왼쪽에서 오른쪽으로 보았을때
	s=e=-1;
	for (int i=0; i<N; i++) {
		if (!visited[(N+i-1)%N] && visited[i]) s = i;
		if (visited[i] && !visited[(i+1)%N]) e = i;
	}
	if (s == -1) s=0,e=N-1;
	int sh=0;
	if (s > e) {
// 쉬프트 해야 하는 횟수
		sh = (N-s);
		for (int i=0; i<N; i++) tmp[i] = arr[i];
		for (int i=0; i<N; i++) arr[i] = tmp[(N+i-sh)%N];
		s=(s+sh)%N, e=(e+sh)%N;
	}
// 뒤집기
	reverse(arr+s, arr+e+1);
// 시작 지점 찾아서 오른쪽으로 밀기
	for (int i=0; i<N; i++) {
		if (arr[i] == 1) {
			printf("%d\n", N-i);
			break;
		}
	}
	printf("%d %d\n", s+1, e+1);
	printf("%d\n", (sh)? sh:N);
	return 0;
}