[BOJ 2352] 반도체 설계

https://www.acmicpc.net/problem/2352

2352번: 반도체 설계

---

위 그림에서 왼쪽의 포트가 연결된 오른쪽 포트의 번호를 A[i]라고 하고, 선택된 오른쪽 포트를 모아놓은 리스트를 L이라고 두면, 

 

가장 많은 포트를 고르기 위해서는 리스트 L의 원소들이 정렬되어 있는 상태에서 크기가 가장 커야 한다.

 

예를 들어, 왼쪽 포트 1부터 차례대로 선택할 때, 오른쪽의 3번 포트가 선택되면, 어떤 방법으로도 왼쪽 5, 6은 오른쪽 1, 2에 꼬이지 않게 연결될 수 없다.

 

즉, 왼쪽이 오른쪽에 연결된 정보 A가 주어질 때, A안에서 증가하는 부분 수열을 찾으면 된다.  LIS를 찾는 문제가 된다.

---

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n;

int main()
{
	scanf("%d", &n);

	vector<int> dp;
	for (int i = 1; i <= n; i++)
	{
		int t;
		scanf("%d",&t);
		if (dp.size() == 0||t > dp.back()) dp.push_back(t);
		else
		{
			vector<int>::iterator it = lower_bound(dp.begin(), dp.end(), t);
			*it = t;
		}
	}

	printf("%lu", dp.size());

}