[백준2352] 반도체 설계 - 자바

해결 방법: DP - LIS(Longest Increasing Subsequence) 최장 증가 수열 2352번 문제는 LIS 개념을 알고 있으면 쉽게 해결 할 수 있다. LIS는 여기를 참고하면 된다.'겹침'은 (a1,a2)*, (b1, b2) 가 있을 때 , a1>b1 일 때 b1<b2 이면 발생한다. *: (왼 포트 번호, 오 포트 번호) 따라서, 인덱스가 증가하는 순서대로 뽑으면서, 수의 크기가 점점 증가하는 형태의 부분 수열 중 가장 긴 것을 찾으면 된다. 예를 들어, 4 ,2 6 , 3 , 1 ,5가 있으면 '2 , 3, 5' 를 뽑는 것이다. 즉, 증가하는 형태로 가장 긴 것을 찾는 것은 결국 겹치지 않은 채로 가장 많은 연결 쌍을 찾는 것과 동일하다. (29번 라인 ~ 43번 라인..........

원문링크 : [백준2352] 반도체 설계 - 자바