ImJay

[BOJ/Java] 12015. 가장 긴 증가하는 부분 수열 2 12015번: 가장 긴 증가하는 부분 수열 2첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)www.acmicpc.net문제 해석주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾는 고전적인 문제의 확장판이다. 이 문제는 수열의 길이가 매우 클 수 있기 때문에 𝑂(𝑁^2)의 시간 복잡도를 갖는 기본적인 동적 프로그래밍 방법으로는 효율적으로 해결할 수 없다. 대신, 이진 탐색을 활용한 𝑂(𝑁log⁡𝑁) 시간 복잡도의 풀이가 필요하다.풀이 과정입력 받기: 수열의 크기 N과 수열 A를 입력 받는다.DP 배열 초기화..