고정 길이 뒤집기 정렬
면접 대비시간 제한2초메모리 제한128 MB
최대 8개의 수로 이루어진 순열을 길이 K의 구간 뒤집기만으로 정렬하는 데 필요한 최소 횟수를 구하고 불가능하면 -1을 출력합니다.
문제
1부터 N까지의 정수가 한 번씩 등장하는 길이 N의 순열이 있다.
한 번의 조작에서는 시작 위치 하나를 고르고, 그 위치부터 오른쪽으로 연속한 K개의 수를 정확히 뒤집는다. 따라서 선택한 위치에서 K개의 수가 모두 순열 안에 들어와야 한다. 예를 들어 순열이 5 4 3 2 1이고 K가 3일 때, 두 번째 위치부터 뒤집으면 5 2 3 4 1이 된다.
주어진 순열을 오름차순으로 만들기 위해 필요한 조작 횟수의 최솟값을 구하자. 오름차순으로 만들 수 없다면 -1을 출력한다.
입력
첫째 줄에 N과 K가 주어진다. 둘째 줄에 순열을 이루는 N개의 정수가 주어진다.
출력
필요한 조작 횟수의 최솟값을 출력한다. 오름차순으로 만들 수 없다면 -1을 출력한다.
제한
- 2 ≤ K ≤ N ≤ 8