20192번 - 순서 섞기 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 1334 | 377 | 281 | 28.557% |
문제
정수가 저장된 크기 N인 배열 A가 있을 때, ‘순서 섞기’ 연산은 아래와 같이 정의된다.
- 크기가 N인 배열 B를 이용하여, 배열 A의 좌측 끝 또는 우측 끝에 있는 값 중 하나를 차례로 꺼내어 배열 B에 좌측부터 순서대로 저장한다. 아래의 그림에서 값이 꺼내지는 순서는 9, 34, 19, 12, 25, 4, 5, 36이다.
- 배열 B를 배열 A에 복사한다.
위에서 보인 그림처럼 순서 섞기 연산을 하면 배열 A의 값은 다음과 같이 변경된다.
(34, 19, 5, 36, 4, 25, 12, 9) =⇒ (9, 34, 19, 12, 25, 4, 5, 36)
배열 A의 i번째 원소를 Ai라고 나타내자. “1 ≤ i < j ≤ N이면 Ai ≤ Aj이다.”가 성립할 때, “배열 A는 단조증가한다”라고 말한다.
정수가 저장된 크기 N인 배열 A가 주어질 때, 배열 A가 단조증가하도록 정렬하기 위해 필요한 ‘순서 섞기’ 연산의 최소 횟수를 계산하는 프로그램을 작성하시오.
입력
첫 번째 줄에 정수 N이 주어진다.
두 번째 줄에 배열 A에 저장된 N개의 정수 A1, ..., AN이 공백을 사이에 두고 차례대로 주어진다.
출력
배열 A가 단조증가하도록 정렬하기 위해 필요한 ‘순서 섞기’ 연산의 최소 횟수를 출력한다.
제한
- 1 ≤ N ≤ 300 000
- 1 ≤ Ai ≤ 109
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | N ≤ 8 |
| 2 | 9 | 답이 2 이하 |
| 3 | 22 | Ai ≤ 2 |
| 4 | 18 | 모든 Ai가 서로 다름 |
| 5 | 47 | 추가 제약 조건 없음 |
예제 입력 1
3 2 2 5
예제 출력 1
0
예제 입력 2
6 1 5 8 10 3 2
예제 출력 2
1
출처
Olympiad > 한국정보올림피아드 > KOI 2020 2차대회 > 고등부 2번
Camp > Petrozavodsk Programming Camp > Winter 2021 > Day 9: Grand Prix of Suwon I번
Contest > Open Cup > 2020/2021 Season > Stage 13: Grand Prix of Suwon I번
- 데이터를 추가한 사람: sharaelong
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호