7256 : LIS 길이 (이분탐색)
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
수열이 주어질 때 가장 긴 증가하는 부분 수열(LIS: Longest Increasing Subsequence)의 길이를 구하십시오.
이분탐색을 활용하면 $O(N \log N)$ 시간에 LIS의 길이를 구할 수 있습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
이분탐색을 활용하면 $O(N \log N)$ 시간에 LIS의 길이를 구할 수 있습니다.
tails 배열을 유지하며, 각 원소를 처리할 때 이분탐색으로 삽입 위치를 결정합니다.[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 수열의 크기 $N$이 주어집니다. ($1 \le N \le 100{,}000$)
둘째 줄에 $N$개의 정수가 주어집니다.
둘째 줄에 $N$개의 정수가 주어집니다.
출력 설명
이 수열의 가장 긴 증가하는 부분 수열(LIS)의 길이를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
8
5 1 4 2 8 3 7 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
tails 배열을 초기화하고, 각 원소 $x$에 대해 bisect_left(tails, x)로 위치를 구합니다. 해당 위치가 tails 끝이면 추가, 아니면 교체합니다. 최종 len(tails)가 LIS 길이입니다.