[C++] 백준 3066번: 브리징 시그널

문제 링크

3066번: 브리징 시그널

문제 요약

두 블록 사이의 포트들을 연결하고자 한다. 이때, 서로 연결되어야 하는 포트들이 주어진다. 이 포트들을 연결할 때, 서로 교차되지 않고 최대로 연결될 수 있는 시그널의 수를 구해야 한다.

접근 방법

전깃줄 문제들이랑 아예 똑같은 쉬운 문제입니다. 위에서부터 내려가면서 일부 포트들을 골라 연결시키려고 합니다. 이때 특정한 포트를 연결하려면 대상이 되는 포트는 위에서 이미 연결된 포트보다 더 아래 있는 포트여야 교차되지 않고 연결이 가능합니다. 그러면 자연스레 가장 긴 증가하는 부분 수열 문제로 볼 수 있습니다.

이 문제의 입력은 40000이기 때문에 $O(N^2)$ 풀이면 TLE를 받을 수 있습니다. 그에 따라서 이분 탐색을 이용하는 $O(NlogN)$ 풀이로 풀어야 합니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int t;
	cin >> t;

	while (t--) {
		int n;
		cin >> n;

		vector<int> seq;
		for (int i = 0; i < n; i++) {
			int num;
			cin >> num;
			if (seq.empty() || seq.back() < num)
				seq.push_back(num);
			else
				seq[lower_bound(seq.begin(), seq.end(), num) - seq.begin()] = num;
		}

		cout << seq.size() << '\n';
	}

	return 0;
}