[알고리즘] C++ 백준 12012 가장 긴 증가하는 부분 수열2

백준 12012

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

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

풀이 전 나의 생각

수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열을 구해야한다.

 

조건

- (1 ≤ N ≤ 1,000,000)

- (1 ≤ Ai ≤ 1,000,000)

 

과정

Ai는 양수이며 100만의 크기를 갖기 때문에 Ai를 담는 배열의 데이터 타입은 int로 설정한다.

수열 A의 크기 N은 100만이지만 2중 for 문만을 이용한 탐색을 진행한다면 100만 * 100만의 계산 횟수로

시간 제한을 맞추지 못한다. 따라서 이분탐색을 이용한 풀이법을 사용해서 답을 구해내야한다.

 

1. 증가하는 수열의 마지막 값보다 크다면 Push, 작다면 lower_bound를 진행하여 나온 위치와 값을 바꾼다.

if (inc_seq.back() < A[i])
		{
			inc_seq.push_back(A[i]);
			ans++;
		}
		else 
		{
			int idx = lower_bound(inc_seq.begin(), inc_seq.end(), A[i]) - inc_seq.begin();
			inc_seq[idx] = A[i];
		}

증가하는 부분 수열을 담을 inc_seq 벡터와 수열의 값이 담긴 A[i] 가 있다.

 

수열 A[i]를 처음부터 탐색하며 증가하는 부분 수열의 벡터 마지막 값보다

현재 A[i]의 값이 더 크다면 값을 Push 한다. -> 증가하는 부분수열을 구하는 과정

ex) inc_seq = {10, 20, 30}, A[i] = 40 -> inc_seq = {10, 20, 30, 40}

 

반대로 증가하는 부분 수열의 벡터 마지막 값보다 현재 A[i]의 값이 작거나 같다면 

증가하는 부분 수열의 이분 탐색 lower_bound를 진행하여 나온 위치에 현재 A[i] 값을 넣어준다.

 

lower_bound를 사용하는 이유

증가하는 부분 수열 {10, 20} 에 수열의 값 18을 넣는다고 가정하면

lower_bound의 값은 20의 다음 위치인 2를 가리키고 {10, 20, 18} 이 될 것이다.

->

{10, 20}일때  Push과정이므로 현재 최종값은 길이 2다.

다음은 18이 들어간 이분 탐색 과정이기 때문에 현재 증가하는 부분 수열은 {10, 20, 18} 이지만

증가하는 부분 수열의 마지막 값을 갱신해줬기 때문에 최종값의 길이 2를 가져가면서

현재 증가하는 부분수열이 {10, 18} 이 된 것 같은 결과를 내주게된다. 

 

여기서 이전에 나왔던 20을 넣어줘도 마지막 값이 18로 갱신되서 {10, 20, 18, 20} 의 최종값 길이 3을

올바르게 구해낼 수 있고 다른 경우로 {10, 20}인 상태에서 20을 넣어준다고 해도 이미 20이 존재하는

위치를 가리켜 중복값을 방지해준다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

int A[1000001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int N, ans = 0;
	vector<int>inc_seq;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}

	inc_seq.push_back(0);

	for (int i = 0; i < N; i++)
	{
		if (inc_seq.back() < A[i])
		{
			inc_seq.push_back(A[i]);
			ans++;
		}
		else 
		{
			int idx = lower_bound(inc_seq.begin(), inc_seq.end(), A[i]) - inc_seq.begin();
			inc_seq[idx] = A[i];
		}
	}

	cout << ans;
}