오답 여부: o 편집 시간: 2022년 3월 14일 오후 7:59
코드
Algorithm/12015.py at main · Junroot/Algorithm
Algorithm/12015-2.py at main · Junroot/Algorithm
풀이
잘못된 풀이
11053 기존에 이 문제에서 수열의 크기가 1000000으로 늘어났다. 즉, nlogn으로 풀어야된다는 뜻이다. 기존문제에서 dp를 사용해서 O(n^2)였는데 dp를 빠르게 구하기 위해서 수열의 크기가 큰것부터 비교하기위헤 우선순위 큐를 사용했다. 하지만 이는 최악의 경우 O(n^2logn)으로 오히려 더 느려진다는 문제가 있었다.
맞는 풀이
완전히 다른 방법으로 접근해야되었다.
그리디 + dp + 바이너리서치를 사용해야되는 문제다.
길이가 같은 두 수열이 있을때, 마지막 수가 더 작은 수열이 앞으로 더 길어질 수 있다는 것은 쉽게 이해할 수 있다.
그래서 수열의 각 길이에서 마지막 값을 dp로 관리하면서 풀면 된다. 자세한 풀이는 아래 링크를 참고하자.
다음 숫자를 추가할 때, 가장 긴 수열의 마지막값보다 크면 새로운 길이의 수열이 만들어지고, 그외의 경우에는 lower bound를 찾아서 그값을 갱신해주면 된다.