백준 2352번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	골드 2

사진을 누르면 문제로 이동합니다.

---

풀이

 밀린 문제 정리하기. 이번에도 LIS이다.

 

 해당 문제를 요약하면 왼쪽 포트에서 오른쪽 포트로 연결되있는 연결선이 꼬이지 않도록 최대한 많이 연결할 때, 연결선의 개수를 구하는 문제다. 문제 설명이 이래서 그렇지 결국 연결되어야 하는 포트에서 LIS를 찾으면 그것이 최대 길이이자 답일 것이다. LIS이기 때문에 중간에 연결선이 교차될리가 없고, 최대 개수를 구하기 때문이다.

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;

int n;
vector<int> arr;

void input() {
	cin >> n;
	arr.resize(n);
	for(int& x : arr) cin >> x;
}

void sol() {
	vector<int> lis{0}, dp(n, 0);

	for(int i = 0; i < n; i++) {
		if(lis[lis.size() - 1] < arr[i]) {
			lis.push_back(arr[i]);
			dp[i] = lis.size() - 1;
		}
		else {
			int idx = lower_bound(ALL(lis), arr[i]) - lis.begin();
			lis[idx] = arr[i];
			dp[i] = idx;
		}
	}
	cout << lis.size() - 1;
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	input();
	sol();
}