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

 

이 문제를 풀어야지 풀어야지 하다가 이제야 하게 되었다.

그런데 잘 몰라서 다른 분의 풀이를 보고 공부한 후 내가 따로 작성해보았다.

 

문제 12015번

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

 

일단 벡터에 입력값을 받아준다. 그런 후 수열을 저장할 벡터에 첫번째 값을 넣어준다. 1부터 N까지 반복문을 돌려주며 수열을 저장할 벡터(result) 마지막값과 입력값을 받아준 벡터(a) i번째 값을 비교해준다. 비교했을 때 a[i]가 마지막값보다 크면 그대로 그 값을 result에 포함시켜준다.

 

그러나 만약 a[i]가 마지막값보다 작거나 같으면 이분탐색을 이용하여 바꿔줄 값의 인덱스를 알아낸다(getIndex).

-> result[mid]가 key(a[i])보다 크거나 같다면 right를 mid 위치로 이동시킨다. 그렇지 않다면 result값을 키워야하기 때문에 left를 mid+1로 이동시킨다.

 

그렇게 완성된 수열이 저장된 벡터의 크기를 출력하면 원하는 값을 얻을 수 있다.

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

int N, index;
vector<int> a, result;

int getIndex(int key) {
	int left = 0, right = result.size() - 1, mid;

	while (left < right) {
		mid = (left + right) / 2;
		if (result[mid] >= key) {
			right = mid;
		}
		else {
			left = mid + 1;
		}
	}

	return right;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		a.push_back(num);
	}
	result.push_back(a.front());	//처음값을 넣어줌

	for (int i = 1; i < N; i++) {
		if (result.back() < a[i]) {	//마지막값보다 크면 수열에 넣어주기
			result.push_back(a[i]);
		}
		else {
			index = getIndex(a[i]);
			result[index] = a[i];
		}
	}

	cout << result.size();

	return 0;
}

 

 

 

[참고] https://velog.io/@junttang/BOJ-12015-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-2-%ED%95%B4%EA%B2%B0-%EC%A0%84%EB%9E%B5-C