원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
수열 정렬하기
원제: 수열 정렬하기
문제
길이가 인 수열 이 주어진다. 여러분은 다음과 같은 시행을 번 이상 자유롭게 할 수 있다.
- 양의 정수 를 정한다.
- 수열 의 원소 중 값이 이하인 원소들을 원래 순서대로 추출하여 부분 수열 를 만든다.
- 수열 의 원소 중 값이 초과인 원소들을 원래 순서대로 추출하여 부분 수열 를 만든다.
- 기존 수열 를, 와 를 순서대로 이어 붙인 수열()로 대체한다.
수열 를 비내림차순()으로 정렬하기 위해서 최소 몇 번의 시행이 필요한지 계산하는 프로그램을 작성하라.
제약 조건을 만족하는 모든 입력에 대해, 주어진 시행을 통해 수열을 비내림차순으로 정렬하는 방법이 존재함을 증명할 수 있다.
제약 조건
- 주어지는 모든 수는 정수이다.
- 정수 ()에 대하여
부분문제
- (6점) 정수 ()에 대하여
- (15점)
- (23점)
- (27점)
- (33점) 정수 , ()에 대하여
- (46점) 추가 제약 조건 없음.
입력 형식
첫 줄에 정수 이 주어진다.
그다음 줄에 개의 정수 이 공백으로 구분되어 차례대로 주어진다.
출력 형식
첫 줄에 수열 를 비내림차순으로 정렬하기 위해 필요한 최소 시행 횟수를 출력한다.
예제
예제 1
6 3 4 5 1 2 6
1
다음과 같이 번의 시행으로 수열 를 비내림차순으로 정렬할 수 있다.
- 로 정하자.
- 값이 이하인 원소들을 원래 순서대로 추출하면 .
- 값이 초과인 원소들을 원래 순서대로 추출하면 .
- 따라서, 수열 는 로 대체된다.
예제 2
9 1 5 9 9 5 1 1 5 9
2
다음과 같이 번의 시행으로 수열 를 비내림차순으로 정렬할 수 있다.
- 으로 정하자.
- 값이 이하인 원소들을 원래 순서대로 추출하면 .
- 값이 초과인 원소들을 원래 순서대로 추출하면 .
- 따라서, 수열 는 로 대체된다.
- 로 정하자.
- 값이 이하인 원소들을 원래 순서대로 추출하면 .
- 값이 초과인 원소들을 원래 순서대로 추출하면 .
- 따라서, 수열 는 로 대체된다.
번보다 적은 횟수의 시행으로는 수열 를 비내림차순으로 정렬하는 것이 불가능함을 증명할 수 있다.