[BOJ] 2352. 반도체 설계
LIS를 이용하여 푸는 문제였다. 예를 들어 1-4 를 연결시켰다고 가정해보면 이제 다음 부터 연결할 수 있는 거는 좌측의 4보다 큰 값을 가진 선만 연결할 수 있게 된다. 따라서 이 문제는 자동적으로 최장 증가 수열의 길이를 찾는 문제가 된다. LIS를 만들 수 있는 방법은 크게 두가지 dp와 lower_bound가 있다. dp의 경우 n^2의 시간복잡도를 가지고, lower_bound는 nlogn의 시간복잡도를 가지는 이문제의 경우 n의 최대값이 40000이기 때문에 dp말고 lower_bound 기법을 적용하여 풀 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36..
