[C/C++] 백준 - 12015번 : 가장 긴 증가하는 부분수열2

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

12015번: 가장 긴 증가하는 부분 수열 2

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

 

https://wonsjung.tistory.com/137

동적 계획법 - LIS (가장 긴 증가하는 부분 수열)

바로 전에 올렸던 위 게시물 내용에 대한 문제가 존재했었다!

전에 해결했었던 방법으로는 O(n^2)이기 때문에 위 문제의 해결방안이 될 수 없다. n의 최대값이 1,000,000이기 때문에 무조건 시간초과가 난다. 그렇기에 O(nlogn)기법으로 해결해야한다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#define INF 9876543210
#define ENDL cout << endl;
#define endl '\n'
#define swap(type, x, y) do{type t=y;y=x;x=t;}while(0)
using namespace std;

typedef long long ll;
typedef pair<int, int> pl;

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

	int N;
	cin >> N;

	vector<int> Answer;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		if (Answer.empty()) Answer.push_back(x);
		else {
			int Data = Answer.back();
			if (Data < x) {
				Answer.push_back(x);
			}
			else {
				int pos = lower_bound(Answer.begin(), Answer.end(), x) - Answer.begin();
				Answer[pos] = x;
			}
		}
	}
	cout << Answer.size() << endl;

	
	return 0;
}