20309번 - 트리플 소트 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 1127 | 691 | 531 | 59.663% |
문제
알고리즘 수업을 듣고 감명받은 윤이는 자신만의 정렬 알고리즘을 만들기로 했다. 윤이가 만든 정렬 알고리즘 "트리플 소트"는 다음과 같이 동작한다.
- 배열에서 연속한 위치에 있는 세 원소를 임의로 고른다.
- 세 원소의 순서를 뒤집는다. 예를 들어 세 원소가 순서대로 $a, b, c$이면 뒤집은 뒤에는 $c,b,a$가 된다.
- 배열이 오름차순으로 정렬될 때까지 위 과정을 반복한다.
하지만 윤이는 트리플 소트로 모든 배열을 정렬할 수 없다는 사실을 깨닫고 실망했다. $1$부터 $N$까지의 정수가 한 번씩 등장하는 배열이 주어졌을 때, 트리플 소트로 정렬할 수 있는지 판별하는 프로그램을 작성하시오.
입력
첫 번째 줄에 배열의 크기를 나타내는 정수 $N$이 주어진다.
두 번째 줄에 배열의 원소가 공백을 사이에 두고 순서대로 주어진다.
출력
트리플 소트로 주어진 배열을 오름차순으로 정렬할 수 있으면 YES, 그렇지 않으면 NO를 출력한다.
제한
$3\leq N \leq 300,000$
$1$ 이상 $N$ 이하의 정수가 주어진 배열에 한 번씩 등장한다.
서브태스크 1 (10점)
$N$은 $3, 4, 5$ 중 하나이다.
서브태스크 2 (90점)
추가적인 제약 조건이 없다.
예제 입력 1
5 1 4 5 2 3
예제 출력 1
YES
다음과 같이 트리플 소트를 통해 배열을 정렬할 수 있다.
- $2, 3, 4$번째 원소의 순서를 뒤집으면 배열은 $[1, 2, 5, 4, 3]$이 된다.
- $3, 4, 5$번째 원소의 순서를 뒤집으면 배열은 $[1, 2, 3, 4, 5]$가 된다. 배열이 오름차순으로 정렬되었으므로 알고리즘을 종료한다.
예제 입력 2
5 3 1 5 2 4
예제 출력 2
NO
출처
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호