백준 12015 - 가장 긴 증가하는 부분 수열2(복습)

문제 링크입니다 https://www.acmicpc.net/problem/12015

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제입니다.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4입니다.

 

가장 긴 증가하는 부분수열 4번과는 다르게 범위가 1,000,000입니다. 따라서 이중 for문을 사용한다면 시간초과가 됩니다. 따라서 다른 방법인 이분 탐색을 이용해야 합니다.

 

만약 10, 20 ,50, 40, 45, 46, 30, 70 인 수열이 있다고 가정하겠습니다.

이때 긴 부분 수열은 10, 20, 40, 45, 46, 70입니다.

배열은 1부터 N까지 반복하면서 큰 수를 vector에 push하는 것이 기본적인 방법입니다.

첫번째로 10을 백터에 넣습니다. 다음 20은 10보다 크기 때문에 백터에 다시 넣습니다. 50도 마찬가지로 넣습니다. 40은 50보다 작기에 넣지 않습니다. 이렇게 전의 수보다 큰 수만 집어 넣는다면 백터에는 10, 20, 50, 70 이 있을 것입니다. 하지만 이 수열은 가장 큰 수열이 아닌 것을 알 수 있습니다.

이러한 상황을 없애기 위해서 다시 40일때로 돌아가겠습니다. 이때는 50을 제외하고 40을 넣어야 합니다. 즉, 큰 수중에서 작은 수를 집어 넣는 것이 문제의 해결 방법 입니다.

 

위의 예시를 이용해 흐름을 보자면

input 10            vector -> (10)

input 20            vector -> (10,20)

input 50            vector -> (10,20,50)

input 40            vector -> (10,20,40)

input 45            vector -> (10,20,40,45)

input 46            vector -> (10,20,40.45,46)

input 30            vector -> (10,20,30,45,46)

input 70            vector -> (10,20,30,45,46,70)      입니다.

 

숫자가 입력될때 백터의 마지막 수와 비교해 크다면 push를 해주면 됩니다.

하지만 마지막 수보다 작다면 마지막 수를 입력 받은 수로 바꿔주면 됩니다. -> 이분 탐색을 사용!!

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;

int num;
int number[1000001];
vector<int> max_;


void binary_searchs(int x) {
	int start = 0;
	int finish = max_.size()-1;
	int mid = 0;
	int ret = 100000007;
	while (start <= finish) {
		mid = (start + finish) / 2;
		if (max_[mid] >= x) {
			if (ret > mid) ret = mid;
			finish = mid - 1;
		}
		else {
			start = mid + 1;
		}
	}
	max_[ret] = x;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> num;
	for (int i = 1; i <= num; i++) {
		cin >> number[i];
	}
	max_.push_back(number[1]);
	for (int i = 2; i <= num; i++) {
		if (max_.back() < number[i]) {
			max_.push_back(number[i]);
		}
		else {
			binary_searchs(number[i]);
		}
	}
	cout << max_.size();
	return 0;
}

 

질문 및 조언 댓글 남겨주세요