수열 정렬하기
골드 IV의견: 0
길이가 \(N\)인 수열 \(A = [A_1, A_2, \cdots, A_N]\)이 주어진다. 여러분은 다음과 같은 시행을 \(0\)번 이상 자유롭게 할 수 있다.
- 양의 정수 \(x\)를 정한다.
- 수열 \(A\)의 원소 중 값이 \(x\) 이하인 원소들을 원래 순서대로 추출하여 부분 수열 \(B\)를 만든다.
- 수열 \(A\)의 원소 중 값이 \(x\) 초과인 원소들을 원래 순서대로 추출하여 부분 수열 \(C\)를 만든다.
- 기존 수열 \(A\)를, \(B\)와 \(C\)를 순서대로 이어 붙인 수열(\(B + C\))로 대체한다.
수열 \(A\)를 비내림차순(\(A_1 \le A_2 \le \cdots \le A_N\))으로 정렬하기 위해서 최소 몇 번의 시행이 필요한지 계산하는 프로그램을 작성하라.
제약 조건을 만족하는 모든 입력에 대해, 주어진 시행을 통해 수열을 비내림차순으로 정렬하는 방법이 존재함을 증명할 수 있다.
- 주어지는 모든 수는 정수이다.
- \(1 \le N \le 300\,000\)
- 모든 \(i\) (\(1 \le i \le N\))에 대하여 \(1 \le A_i \le N\)
첫 줄에 정수 \(N\)이 주어진다.
그다음 줄에 \(N\)개의 정수 \(A_1, A_2, \cdots, A_N\)이 공백으로 구분되어 차례대로 주어진다.
첫 줄에 수열 \(A\)를 비내림차순으로 정렬하기 위해 필요한 최소 시행 횟수를 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 6점 | 모든 \(i\) (\(1 \le i \le N\))에 대하여 \(A_i \le 2\)이다. |
2 | 15점 | \(N \le 15\) |
3 | 23점 | \(N \le 100\) |
4 | 27점 | \(N \le 750\) |
5 | 33점 | 모든 \(i, j\) (\(1 \le i < j \le N\))에 대하여 \(A_i \ne A_j\)이다. |
6 | 46점 | 추가 제약 조건 없음. |
6
3 4 5 1 2 6
1
다음과 같이 \(1\)번의 시행으로 수열 \(A\)를 비내림차순으로 정렬할 수 있다.
\(x = 2\)로 정하자. 값이 \(2\) 이하인 원소들을 원래 순서대로 추출하면 \(B = [1, 2]\)이고, 값이 \(2\) 초과인 원소들을 원래 순서대로 추출하면 \(C = [3, 4, 5, 6]\)이다. 따라서 수열 \(A\)는 \([1, 2, 3, 4, 5, 6]\)으로 대체된다.
9
1 5 9 9 5 1 1 5 9
2
다음과 같이 \(2\)번의 시행으로 수열 \(A\)를 비내림차순으로 정렬할 수 있다.
- \(x = 1\)로 정하자. 값이 \(1\) 이하인 원소들을 추출하면 \(B = [1, 1, 1]\), 값이 \(1\) 초과인 원소들을 추출하면 \(C = [5, 9, 9, 5, 5, 9]\)이다. 따라서 수열 \(A\)는 \([1, 1, 1, 5, 9, 9, 5, 5, 9]\)로 대체된다.
- \(x = 5\)로 정하자. 값이 \(5\) 이하인 원소들을 추출하면 \(B = [1, 1, 1, 5, 5, 5]\), 값이 \(5\) 초과인 원소들을 추출하면 \(C = [9, 9, 9]\)이다. 따라서 수열 \(A\)는 \([1, 1, 1, 5, 5, 5, 9, 9, 9]\)로 대체된다.
\(2\)번보다 적은 횟수의 시행으로는 수열 \(A\)를 비내림차순으로 정렬하는 것이 불가능함을 증명할 수 있다.
riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2026 > 1차 대회 > 초등부 3번 / 중등부 2번
평가 및 의견
수열 정렬하기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
수열 정렬하기