[백준 12015] 가장 긴 증가하는 부분 수열 2

문제 링크 => 12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net)

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

---

이 문제는 이분 탐색을 이용하는 문제이다.

 

이전에 해결하였던 문제를 동일하게 적용한다면 시간 초과가 난다. (n값이 1,000,000 으로 주어짐)

 

vector<int> v 를 활용하여 다음과 같은 방법으로 배열에 있는 값들을 push하도록 한다.

• 현재 벡터 v의 원소들에 대하여 arr[i] 값이 있는지를 lower_bound를 이용하여 구한다.
• lower_bound를 이용하여 얻어낸 index값이 벡터 v에 존재하지 않는 경우 push_back한다. (즉, index 값이 v.size() 인 경우)
• 벡터 v 내에 존재하는 경우 해당 index의 원소를 arr[i] 값으로 변경해준다.

이 방법을 예제를 통해 적용해보도록 하자.

 

6

10 20 10 30 20 50

 

arr[i]	index	vector<int> v
arr[0]=10	0	[ 10 ]
arr[1]=20	1	[ 10, 20 ]
arr[2]=10	0	[ 10, 20 ]
arr[3]=30	2	[ 10, 20, 30 ]
arr[4]=20	1	[ 10, 20, 30 ]
arr[5]=50	3	[ 10, 20, 30, 50 ]

이때 index는 lower_bound(v.begin(), v.end(), arr[i]) - v.begin() 값이다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

int arr[1000000];

void solve(int n) {
	vector<int> v;

	for (int i = 0; i < n; i++) {
		int index = lower_bound(v.begin(), v.end(), arr[i]) - v.begin();
		if (index == v.size()) v.push_back(arr[i]);
		else if (index < v.size()) v[index] = arr[i];
	}

	cout << v.size() << endl;
}

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

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	solve(n);
	
	return 0;
}