테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 트리플 소트 ======

===== 풀이 =====
  * 두칸 간격의 원소를 스왑하는 연산이다. 연산을 아무리 반복해도, 홀수번째 위치의 원소는 계속 홀수번째 위치에, 짝수번째 위치의 원소는 계속 짝수번째 위치에 놓이게 된다. 주어진 수열에서, 홀수 원소가 짝수번째 위치에 놓여져있거나 반대인 경우가 있으면, 이 원소를 올바른 위치로 옮길수 없으므로 정렬이 불가능하다.
  * 위의 조건을 통과해서, 홀수 원소들은 모두 홀수번째 위치에, 짝수 원소들은 모두 짝수번째 위치에 놓여져있다면, 홀수번째 원소들과 짝수번째 원소들을 각각 따로 정렬한다고 생각해도 된다. 홀수번째 원소들만 대상으로 연산을 수행하면, 실질적으로는 인접한 원소를 스왑하는 효과가 된다. 인접한 원소를 스왑하는 연산으로는 수열을 정렬시키는 것이 가능하므로, 이 경우는 무조건 정렬이 가능하다.
  * 결국 모든 홀수 원소가 모두 홀수번째 위치에 놓여져 있는지만 확인하면 된다. 1~N까지의 수로 구성되어 있으므로, 전체 원소를 확인할필요 없이 절반만 확인해도 된다. 시간복잡도는 O(n)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 20309. 트리플 소트".

- Problem link: https://www.acmicpc.net/problem/20309
- Solution link: http://www.teferi.net/ps/problems/boj/20309

Tags: [invariant]
"""


def main():
    _N = int(input())
    arr = [int(x) for x in input().split()]
    is_sortable = all(x % 2 == 1 for x in arr[::2])
    print('YES' if is_sortable else 'NO')


if __name__ == '__main__':
    main()
</dkpr>


{{tag>BOJ ps:problems:boj:실버_3}}