[C++] G2 백준 12015 - 가장 긴 증가하는 부분수열(LIS) 2 (클래스5)

1. 문제 링크

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

소요 시간 : 2시간 이상

시도 횟수 : 7

 

2. 문제 설명

난이도 : G2

사용 알고리즘 : 이분탐색

가장 긴 증가하는 부분수열 문제(LIS, 11053)보다 입력값으로 주어지는 수열의 크기와 수열을 이루는 각 숫자의 범위가 1000배 커졌다.

 

3. 풀이 방식 및 해결

당연히 LIS 1 문제를 풀 때 코드를 그대로 한 번 테스트해봤다. 역시나 시간초과

해당 코드를 약간 변형을 해서, DP 대신 vector에 저장하고 sort하는 방식으로 바꿔 보았으나, 이 또한 시간 초과가 발생.

고민을 한 시간정도 했는데,,방식이 잘 떠오르지 않아서 질문 게시판에 다른 사람들이 어떻게 했는지 참고를 해봤다.

c++에 upper_bound, lower_bound라는 함수가 있다고 하는데, 이런 함수는 처음 보았기에 나중에 검색해보자! 하고 다른 풀이를 참고하였다.(해당 함수는 아래 4번에 설명)

 

풀이 방법은 아래와 같다.

1. 벡터의 마지막 값보다 큰 값(tmp)이 들어오면 그 뒤에 추가한다.

2. 그렇지 않다면, 아래 과정을 따른다

    2-1. 배열에서 tmp보다 큰 값중 가장 작은 값을 찾는다(여기서 이분 탐색)

    2-2. 해당 값을 tmp로 바꿔준다

이렇게 하면 배열의 오름차순이 정렬되면서, 각 시점에 가장 긴 증가하는 수열임이 보장된다 !

 

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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

	int n;
	cin >> n;
	int tmp;
	vector<int> v;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		if (i > 0 && v.back() >= tmp) {
			int left = 0, right = v.size() - 1;
			while (left<right) {
				int mid = (left + right) / 2;
				if (v[mid] < tmp) left = mid + 1;
				else right = mid;
			}
			v[right] = tmp;
		}
		else v.push_back(tmp);
	}
	cout << v.size();
}

 

4. lower_bound, upper_bound

c++에서 제공하는 이분 탐색 함수이다.

lower_bound(begin, end, key) : 찾으려는 key값 "이상"의 숫자가 배열에서 처음 등장하는 위치를 반환한다.

upper_bound(begin, end, key) : 찾으려는 key값을 "초과"하는 숫자가 배열에서 처음 등장하는 위치를 반환한다.

이 함수를 활용하면 이분탐색이 한 줄로 끝난다는 점,,

문제에 따라 배열이 정렬된 상태여야 할 수도 있다는 점만 주의하면 될 듯 !

 

<오늘의 TMI>
경기도 청년 면접 수당을 신청했다.
지역 화폐로 지급되는 방식이라 고양페이 카드도 신청했기에 이제 열심히 나가서 먹어야 한다(?)

<오늘의 노래 추천>
음율 "피차일반"
음율의 청량한 목소리 + 화려한 세션 사운드 + 힘이 되는 가사의 삼박자가 어우러집니다!