이분탐색dp (1) 썸네일형 리스트형 [백준/C++] 14003번 가장 긴 증가하는 부분 수열 5 풀이 문제 해석 문제 풀이 우선 수열의 크기가 100만이라서 O(N2) 풀이로는 해결할 수 없다. dp +이분탐색을 이용한 O(NlogN) 풀이 방법이 필요하다. 풀이 방법은 14002번을 풀어보면 알 수 있는데 DP 배열을 1차원으로 사용한다고 생각해보면 될 것 같다. 지금 숫자가 내가 가진 숫자 최대값보다 크다면 배열의 마지막 값으로 추가한다. (코드상 order 배열) 지금 숫자가 최대값보다 작다면 이분탐색을 통해 지금 숫자보다 큰 최소값과 교환해준다. 이 때 1차원 DP의 경우 값을 덮어 씌워가며 계산을 진행하는게 정석인데, 가장 긴 증가하는 부분 수열의 길이를 찾을 때 바뀌어나간 값들의 길이가 최대가 되지 않는 이상 길이 자체에는 영향을 미치지 않는다. 여기까지가 14002번의 문제 풀이다. 그러나 .. 이전 1 다음
