백준 2352 반도체 설계
-
BOJ 2352 반도체 설계Algorithm/BOJ 2020. 6. 12. 16:10
출처: www.acmicpc.net/problem/2352 분류: Greedy, LIS 접근방식 포트에 선이 서로 꼬이지 않게 연결하려고 할 때 가장 많이 연결할 수 있는 개수를 찾는 문제입니다. 문제의 예처럼 이렇게 연결되어 있을 때, 왼쪽을 A포트 오른쪽을 B포트라고 생각해보겠습니다. A[1] -- B[4] 포트가 연결되어 있다면 왼쪽에서 A[1]을 제외한 나머지 포트들은 모두 1보다 크기 때문에 B에서 4보다 작은 포트들에는 연결할 수가 없습니다. 다시말해 A[i] 포트 --> B[j] 포트로 연결하려고 할 때 현재까지 B에 연결되어있는 포트 중 가장 큰 녀석보다 작은 경우에는 연결할 수가 없게 됩니다. 즉, 이 경우엔 B에 연결해야 하는 포트들 중에서 연속적으로 증가하는 수의 최대 길이가 몇이야?..