포스택

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

"""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()

• Dependency: teflib.seqtask.longest_dec_subseq_length