본문 바로가기
728x90

가장 긴 증가하는 부분수열1

[python] 백준 12738 가장 긴 증가하는 부분 수열 3 https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 해결 이진 탐색에서 bisect 의 bisect_left를 사용할줄 아는지 문제 bisect_left(A,num) 은 A 리스트에서 num이상의 수가 최초로 나오는 인덱스를 의미한다. 따라서 bisect_left(dp,num)의 값이 k일 때 dp[k] = num으로 바꾸면서 나아가면 가장 긴 증가하는 부분수열을 dp에 넣을 수 있다. CODE from bise.. 2023. 4. 9.
728x90