문제
중복이 없는 정수 수열이 주어진다.
이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다.
이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다.
그런데, 같은 수열도 두 가지 이상의 방식으로 정렬할 수 있다.
예를 들어 3 4 1 2 는,
3 4 와 1 2 를 각각 뒤집어 4 3 2 1 을 만든 뒤,
전체를 뒤집어 정렬할 수도 있지만,
4 1 2 를 먼저 뒤집고,
3 2 1 을 다시 뒤집으면 두 번만의 연산으로 정렬할 수도 있다.
정렬을 위해 뒤집기 연산을 최소 몇 번 해야 하는지를 계산하는 프로그램을 작성하라.
입력
입력의 첫 줄에는 수열의 길이 N(1≤N≤8)이 주어진다.
다음 줄에 N개의 정수로 각 수열의 원소들이 순서대로 주어진다.
한 수열에 같은 수가 두 번 출현하지 않는다고 가정해도 좋다.
모든 수는 1부터 1백만 사이의 정수이다.
출력
입력을 정렬하기 위해 필요한 최소 뒤집기 연산의 수를 출력한다.
예제
4
3 4 1 2
2
태그
출처
Online Contest
로그인해야 코드를 작성할 수 있어요.