정렬게임 > 문제은행

본문 바로가기


실전대비 Level4

1316 : 정렬게임

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 20 회    시도횟수: 153 회   



중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. 그런데, 같은 수열도 두 가지 이상의 방식으로 정렬할 수 있다.

 

예를 들어 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백만 사이의 정수이다.



입력을 정렬하기 위해 필요한 최소 뒤집기 연산의 수를 출력한다.


[Copy]
4
3 4 1 2
[Copy]
2





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.