https://www.acmicpc.net/problem/11053 <풀이> 알고스팟에서 같은 문제를 풀어본 적이 있다. 중요한 문제라 다시 한 번 점검하는 차원에서 풀어보았다.
처음에 순간 'O(n^2)으로 풀리지 않을까?' 하는 멍청한 생각이 들었다...
(n의 크기가 1000밖에 안 돼서..) " 1 2 3 4 10 2 3 4 5 6 7 8 " 이 반례를 생각해보면 안 된다는 것을 쉽게 알 수 있다. dp 배열에 어떤 값을 저장할지가 중요하다. 이러한 배열이 있을 때, dp 배열의 원소로는 "나를 포함한, 증가하는 수열의 길이"가 들어가게 된다.
제일 처음 pivot = 10 을 생각해보면, (인덱스 0의 10을 의미) 10 -> 20 -> 30 -> 50 순으로 재..........
원문 링크 : boj_11053_가장 긴 증가하는 부분 수열
