어흥

문제 링크: www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 1. 주의할 점 - LIS 알고리즘에 대해 알고 있어야 한다 - 이분탐색을 통한 LIS를 수행한다 2. 구현 - 모든 수를 Arr[] 배열에 담는다 - DP[idx] 배열에 가장 긴 증가하는 부분수열 중에서 idx번째에 위치한 수를 저장한다 - DP[0] = Arr[0]을 담은 후, 1번째 index부터 탐색을 시작한다 - 만약 DP[Idx]보다 Arr[i]가 크다면, 가장 긴 ..