백준 가장 긴 증가하는 부분 수열 2 120151 [백준] 30. 가장 긴 증가하는 부분 수열 2 12015 해설 가장 긴 증가하는 부분 수열 2 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 갈수록 풀지 못하는 문제가 많아지고 있습니다. 해당 문제도 마찬가지로 풀지 못하였는데 풀이 방법이 전혀 생각지도 못한 방법이면서 너무나 간단하여 스스로 정리할 겸 글을 쓰게 되었습니다. 문제 풀이 이전에 풀었던 가장 긴 증가하는 부분 수열 1의 경우 dp를 통해 시간 복잡도 O(n^2)으로 문제를 해결할 수 있었습니다. 하지만 2의 경우 N의 범위가 1,000,000이기 때문에 다른 방법을 사용해 줘야 됩니다. 정답은 이진 탐색을 .. 2024. 1. 29. 이전 1 다음 반응형
