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

문제

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

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

---

문제 요약

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

ex) 수열 A = {10, 20, 10, 30, 20, 50} 인 경우, 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이다.

---

코드

#include<iostream>
#include<vector>

using namespace std;

int n;

vector<int> arr, res;

// res에서 key보다 큰 수 중 가장 먼저 나온 수의 인덱스 반환 (이진 탐색)
// 같은 수가 있을 경우 그 자리 반환
int mylower_bound(vector<int>& res, int key) {
	int left = 0;
	int right = res.size() - 1;

	int ans = right;

	while (left <= right) {
		int mid = (left + right) / 2;

		if (key <= res[mid]) {
			right = mid - 1;
			ans = mid;
		}
		else {
			left = mid + 1;
		}
	}
	return ans;
}

int main() {
	// 입출력 시간 단축
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

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

	res.push_back(arr[0]); // 초기 res 배열 상태

	// 주어진 배열의 왼쪽 요소부터 체크
	for (int i = 1; i < n; i++) {
		// res의 마지막 요소보다 더 크다면,
		if (res.back() < arr[i]) {
			res.push_back(arr[i]); // res 맨 뒤에 삽입
		}
		else {
			// res에서 가장 먼저 등장하는 arr[i]보다 큰 수의 인덱스
			int idx = mylower_bound(res, arr[i]); 
			res[idx] = arr[i]; // 
		}
	}

	cout << res.size();

	return 0;
}

---

코드 설명

같은 유형의 다른 LIS 문제와는 푸는 방식이 다르다.

기존 LIS 문제들은 2번의 for문으로 O(N^2)에 풀었지만, 이 문제는 N <= 1000000 이므로 불가능하다.

따라서 이진 탐색을 이용한다.

 

1. 먼저 가장 긴 부분 수열 정보를 저장할 벡터 res를 생성하고, 초기 상태로 A[0] 요소를 삽입한다.

+ res는 오름차순으로 저장되며, res의 길이는 가장 긴 부분 수열의 길이를 나타낸다.

 

2. 주어진 수열 A의 왼쪽 요소부터 하나씩 체크하면서, res의 마지막 요소 즉, 현재 res의 가장 큰 값보다 더 큰 값이라면, res에 맨 뒤에 삽입한다.

 

3. 그렇지 않고 res 맨뒤에 삽입이 불가하다면, A[i]보다 큰 값 중 가장 작은 값, 또는 같은 값이 있다면 그 자리에 있는 값을 A[i]로 변경한다.

+ res에서 A[i]보다 큰 값 중 가장 작은 값, 또는 같은 값의 위치를 이진 탐색으로 O(logN)에 찾는다.

 

4. res의 크기를 출력한다.

 

+ res는 가장 긴 부분 수열이 아님에 주의해야 한다.

 

참고: https://hyeo-noo.tistory.com/32