[알고리즘] 2352 반도체 설계

[chongin12]

2352번 반도체 설계

이 문제는 LIS (가장 긴 증가하는 부분 수열)의 응용 문제입니다. 선이 겹치지 않으려면 결국 이전에 선택하는 선은 다음에 선택하는 선보다 항상 작아야 하고, 결국 가장 긴 증가하는 부분 수열이 되어야 합니다. 다이나믹 프로그래밍 기법으로 해결할 수 있습니다.

하지만 이 문제는 $N$ 제한이 $40,000$이고, 정형적인 LIS 문제의 시간복잡도는 $O(N^2)$이기 때문에 $O(NlogN)$ 알고리즘을 사용해야 합니다.

이분탐색을 활용하는 방법과 세그먼트 트리를 활용하는 방법 중 이분탐색을 활용하는 방법으로 문제 풀이를 진행했습니다.

각 숫자가 정확하진 않아도 "이 위치엔 무조건 들어간다!"는 그리디하게 찾을 수 있으므로 각 숫자를 순차적으로 보면서 가변배열 v에 누적시킵니다. 누적시킬 때 현재 숫자를 넣을 수 있다면 해당 값을 치환하고, 가장 큰 값이라면 배열 맨 마지막에 누적시킵니다. 최종적으로 남은 배열의 길이를 출력하면 되며, 이 값은 정답은 아니지만 길이는 정답이 맞습니다.

예시 코드