LIS

[2352] 반도체 설계(C++)

문제 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 🔎 해결 방법 이 문제는 [11053] 가장 긴 증가하는 부분 수열과 같이 왼쪽 포트는 이미 오름차순으로 정렬이 되어 있으므로 이와 연결된 두번째 포트가 어떻게 해야 가장 긴 증가하는 부분 수열을 이루는지를 찾으면 된다. 그래서 처음에는 [11053] 가장 긴 증가하는 부분 수열 문제를 해결한 것과 같이 이중 for문을 사용한 dp로 해결하려고 했다. 하지만 틀렸습니다가 떠서 질문들을 찾아보니 대부분 "LIS" 라는 알고리즘을 사용하여 ..