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

---

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

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

 

11053번 가장 긴 증가하는 부분 수열 문제와 비슷하다.

배열이 커져서 O(n^2) 알고리즘을 못쓰게 된 것이 좀 다르다.

 

사실 모르겠어서 폭풍 구글링을 진행했다.

LIS 알고리즘 너무 어렵다 ㅠㅠ

 

algorithm 헤더에 있는 lower_bound를 이용하여 문제를 풀었다.

lower_bound : 원하는 수 이상인 수가 처음으로 등장하는 위치를 반환

물론 배열을 빼줘야된다(-DP). 아니면 주솟값 나옴!

 

이해가 되기 쉽게 예시 3개를 가져와봤다. (질문게시판)

사실 엄밀히 따지면 LIS 수열을 구하는 알고리즘은 아니다. 길이를 위해 이용됐을 뿐!

 

DP 배열의 길이가 수열의 길이, 즉 정답이다.

 

전체 코드는 아래와  같다.

#include <iostream>
#include <algorithm>
using namespace std;

int DP[1000001];
int N; int idx;

int main() {
	// lower_bound : 원하는 수 이상인 수가 처음으로 등장하는 위치
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	int input; 
	for (int i = 0; i < N; i++) {
		cin >> input;
		if (idx == 0) { // 맨 처음
			DP[idx] = input; // 처음 값 설정
			idx++;
		}
		else {
			if (input > DP[idx - 1]) { // 현재 최댓값보다 클 경우
				DP[idx] = input; //  맨 뒤에 새롭게 값을 넣음
				idx++;
			}
			else {  // 최댓값보다 작으면
				// DP 내에서 대체할 수 있는 인덱스를 찾아야 함
				DP[lower_bound(DP, DP + idx, input) - DP] = input;
			}
		}
	}
	cout << idx;
}