목차
Passport Control
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 16288 |
| 문제명 | Passport Control |
| 레벨 | 골드 3 |
| 분류 |
LIS |
| 시간복잡도 | O(nlogn) |
| 인풋사이즈 | n<=100 |
| 사용한 언어 | Python 3.13 |
| 제출기록 | 35500KB / 44ms |
| 최고기록 | 36ms |
| 해결날짜 | 2025/03/03 |
풀이
- pi기준으로 번호를 바꿔서 수열을 만들면, 결국 하려는 것은 수열을 여러개의 큐에 나눠 담았다가 다시 합치는 방식으로 정렬시키는 것이다.
나연 정렬에서 스택 대신 큐를 사용한 버전이라 생각하면 된다.
- 각 큐에 들어간 원소들의 순서는 바뀔수 없으므로, 각 큐에는 증가하는 순서대로 원소들이 들어가야 하고, 이때 최소 개수의 큐를 사용해서 이 작업을 하는 것은, 수열을 최소 개수의 증가 부분 수열로 나누기와 같다.
- 수열을 커버하기 위해 필요한 증가 부분 수열의 최소 개수를 구하는 것은, longest non-decreasing subsequence의 길이를 구하는 것과 같고, 시간복잡도는 O(nlogn)이다. 구한 값이 k이하이면 정렬이 가능한 것이고, 그렇지 않으면 불가능한 것이다.
코드
"""Solution code for "BOJ 16288. Passport Control".
- Problem link: https://www.acmicpc.net/problem/16288
- Solution link: http://www.teferi.net/ps/problems/boj/16288
Tags: [LIS]
"""
from teflib import seqtask
def main():
_N, k = [int(x) for x in input().split()]
pi = [int(x) for x in input().split()]
count = seqtask.longest_dec_subseq_length(pi, strict=True)
print('YES' if count <= k else 'NO')
if __name__ == '__main__':
main()- Dependency: teflib.seqtask.seqtask.longest_dec_subseq_length