728x90 lower bound 썸네일형 리스트형 [백준알고리즘] 2352번: 반도체 설계 -Python [백준알고리즘] 2352번: 반도체 설계 -Python https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자. www.acmicpc.net 언뜻 봐서는 O(N^2)의 방식의 풀이도 통과할 줄 알았는데 시간 초과가 발생했다. 이 문제는 LIS문제이다. 가장 긴 증가하는 부분 수열을 만들어야 한다. 여기서는 직접 부분 수열을 출력하는 것이 아닌 길이만 출력하면 되기 때문에 간단한 lower .. 더보기 이전 1 다음