백준 14003 C++

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

 

완전히 생소한 개념으로 푸는 문제여서 많이 어려웠다.

가장 긴 증가하는 부분 수열을 구하는 문제였다.

O(nlogn)의 시간 복잡도로 푸는 방법이 있었으며 lower_bound가 어떤 역할을 하는지 명확하게 알아야 풀 수 있는 문제였다.

오랜만에 lower_bound를 사용해서 반갑기도 했고 다시 복습할 수 있는 계기였다.

 

#include <bits/stdc++.h>

using namespace std;

int n, num, len = 0;
const int INF = 1e9 + 4;
int lis[1000010];
pair<int, int> p[1000010];		//num, 얘가 몇번째 index인지.
vector<int> v;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	fill(&lis[0], &lis[0] + 1000010, INF);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		auto lowerPos = lower_bound(lis, lis + len, num);			//num보다 이상의 위치값을 찾음.
		int pos = (int)(lower_bound(lis, lis + len, num) - lis);		//num이상의 숫자가 최초로 나오는 곳이 배열에서 몇번째 index인지 찾음
		if (*lowerPos == INF) len++;		//lowerPos가 가르키는 값이 INF. 즉, num의 이상 값이 없다면 len++;
		*lowerPos = num;
		p[i].first = num;			
		p[i].second = pos;		//얘가 무슨 의미냐? ->  이후에 배열을 돌면서 어떤 값이 이 다음으로 연속되는 값인지 찾기 위해 필요함.
	}

	//cout << "len : ";
	cout << len << "\n";
	//for (int i = 0; i < n; i++) {
	//	cout << p[i].first << " : " << p[i].second << "\n";
	//}

	for (int i = n - 1; i >= 0; i--) {
		if (p[i].second == len - 1) {
			v.push_back(p[i].first);
			len -= 1;
		}
	}
	reverse(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}