테페리넷

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

====== 포스택 ======

===== 풀이 =====
  * 스택을 이용해서 정렬하는 것 같지만, 스택에 먼저 넣은 수가 더 앞에 위치하게 되므로, 결국은 큐를 이용해서 정렬하는 것에 더 가깝게 되고 [[ps:problems:boj:16288]]과 같은 방법으로 풀수 있다.
  * 정렬하는데 필요한 스택의 최소 개수를 O(nlogn) LIS로 구한 뒤에, 그 개수가 4보다 큰지 여부를 확인하면 풀 수 있다.
  * 사실 스택의 개수가 4이하로 작기 때문에, 이진탐색도 필요 없이 그냥 시뮬레이션 돌리다가 스택 4개로 해결이 안되면 종료하는 것으로 구현할수 있고, 이러면 O(n)이 된다. 공식 풀이에서도 이 방법을 설명했다.
    * 물론 이진탐색 LIS로 구하더라도, 중간에 길이가 5이상이 되는 순간 종료하는 방식으로 처리해주면 O(n)으로 줄이는 것은 어렵지 않다..

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 25556. 포스택".

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

Tags: [LIS]
"""

from teflib import seqtask


def main():
    _N = int(input())
    A = [int(x) for x in input().split()]

    print('YES' if seqtask.longest_dec_subseq_length(A) <= 4 else 'NO')


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:seqtask#longest_dec_subseq_length|teflib.seqtask.longest_dec_subseq_length]]

{{tag>BOJ ps:problems:boj:골드_5}}