루미 알고리즘

#1130골드수열 정렬하기수열 정렬하기

KOI 2026 1차코딩초등부 3번, 중등부 2번출제 장근영이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

수열 정렬하기

원제: 수열 정렬하기

문제

길이가 NN인 수열 A=[A1,A2,⋯ ,AN]A = [A_1, A_2, \cdots, A_N]이 주어진다. 여러분은 다음과 같은 시행을 00번 이상 자유롭게 할 수 있다.

  1. 양의 정수 xx를 정한다.
  2. 수열 AA의 원소 중 값이 xx 이하인 원소들을 원래 순서대로 추출하여 부분 수열 BB를 만든다.
  3. 수열 AA의 원소 중 값이 xx 초과인 원소들을 원래 순서대로 추출하여 부분 수열 CC를 만든다.
  4. 기존 수열 AA를, BB와 CC를 순서대로 이어 붙인 수열(B+CB + C)로 대체한다.

수열 AA를 비내림차순(A1≤A2≤⋯≤ANA_1 \le A_2 \le \cdots \le A_N)으로 정렬하기 위해서 최소 몇 번의 시행이 필요한지 계산하는 프로그램을 작성하라.

제약 조건을 만족하는 모든 입력에 대해, 주어진 시행을 통해 수열을 비내림차순으로 정렬하는 방법이 존재함을 증명할 수 있다.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤300 0001 \le N \le 300\,000
  • 정수 ii (1≤i≤N1 \le i \le N)에 대하여 1≤Ai≤N1 \le A_i \le N

부분문제

  1. (6점) 정수 ii (1≤i≤N1 \le i \le N)에 대하여 Ai≤2A_i \le 2
  2. (15점) N≤15N \le 15
  3. (23점) N≤100N \le 100
  4. (27점) N≤750N \le 750
  5. (33점) 정수 ii, jj (1≤i<j≤N1 \le i < j \le N)에 대하여 Ai≠AjA_i \ne A_j
  6. (46점) 추가 제약 조건 없음.

입력 형식

첫 줄에 정수 NN이 주어진다.

그다음 줄에 NN개의 정수 A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N이 공백으로 구분되어 차례대로 주어진다.

출력 형식

첫 줄에 수열 AA를 비내림차순으로 정렬하기 위해 필요한 최소 시행 횟수를 출력한다.

예제

예제 1

입력
6
3 4 5 1 2 6
출력
1

다음과 같이 11번의 시행으로 수열 AA를 비내림차순으로 정렬할 수 있다.

  1. x=2x = 2로 정하자.
    • 값이 x=2x = 2 이하인 원소들을 원래 순서대로 추출하면 B:=[1,2]B := [1, 2].
    • 값이 x=2x = 2 초과인 원소들을 원래 순서대로 추출하면 C:=[3,4,5,6]C := [3, 4, 5, 6].
    • 따라서, 수열 AA는 B+C=[1,2,3,4,5,6]B + C = [1, 2, 3, 4, 5, 6]로 대체된다.

예제 2

입력
9
1 5 9 9 5 1 1 5 9
출력
2

다음과 같이 22번의 시행으로 수열 AA를 비내림차순으로 정렬할 수 있다.

  1. x=3x = 3으로 정하자.
    • 값이 x=3x = 3 이하인 원소들을 원래 순서대로 추출하면 B:=[1,1,1]B := [1, 1, 1].
    • 값이 x=3x = 3 초과인 원소들을 원래 순서대로 추출하면 C:=[5,9,9,5,5,9]C := [5, 9, 9, 5, 5, 9].
    • 따라서, 수열 AA는 B+C=[1,1,1,5,9,9,5,5,9]B + C = [1, 1, 1, 5, 9, 9, 5, 5, 9]로 대체된다.
  2. x=7x = 7로 정하자.
    • 값이 x=7x = 7 이하인 원소들을 원래 순서대로 추출하면 B:=[1,1,1,5,5,5]B := [1, 1, 1, 5, 5, 5].
    • 값이 x=7x = 7 초과인 원소들을 원래 순서대로 추출하면 C:=[9,9,9]C := [9, 9, 9].
    • 따라서, 수열 AA는 B+C=[1,1,1,5,5,5,9,9,9]B + C = [1, 1, 1, 5, 5, 5, 9, 9, 9]로 대체된다.

22번보다 적은 횟수의 시행으로는 수열 AA를 비내림차순으로 정렬하는 것이 불가능함을 증명할 수 있다.

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2026년 1차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.