[백준 12015] 가장 긴 증가하는 부분 수열_이분탐색(C++)

[문제]

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

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

수열이 주어졌을때 가장 긴 증가하는 부분 수열 구하라

그것의 길이를 출력!

 

[나의 문제 접근]

이미 이거슨....dp와 관련된 문제라는 것을 알고있다!!

하지만 어떻게 했더라...기억이 안난다 두달전쯤에 풀었던것으로 기억.. 일단 기억을 더듬어 똑같이 만들어 보기로 했다

 

10	20	10	30	20	50
👆🏻

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]
{10} / 1(크기)	1	1	1	1	1

 

10	20	10	30	20	50
	👆🏻

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]
{10}	{10,20} / 2	1	1	1	1

 

10	20	10	30	20	50
		👆🏻

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]
{10}	{10,20}	{10} / 1	1	1	1

- 전의 값 20 보다 10이 작으므로 그냥 pass

 

10	20	10	30	20	50
			👆🏻

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]
{10}	{10,20}	{10}	{10,20,30} / 3	1	1

-30 이전의 있던 값들 중에 가장 dp값이 컸던(2) 것에 +1 을 해준다. 따라서 dp[4] = 3이된다

 

10	20	10	30	20	50
				👆🏻

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]
{10}	{10,20}	{10}	{10,20,30}	{10,20}	1

 

10	20	10	30	20	50
					👆🏻

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]
{10}	{10,20}	{10}	{10,20,30}	{10,20}	{10,20,30,50}

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

int asize;//수열의 크기

int main() {
	
	cin >> asize;
	
	int max = 1; //0으로 초기화하면 수열의 길이가 1일때 0으로 출력됨
	
	vector<int> a(asize, 0);
	vector<int> dp(asize,1);
	
	for(int i = 0; i < asize; i++){
		cin >> a[i];
	}
	
	for(int i = 0; i < asize; i++){
		for(int j = 0; j < i; j++){
			if(a[i] > a[j] && dp[i] < dp[j] + 1){
				dp[i] = dp[i] +1;
			}
				
			if(max < dp[i])
				max = dp[i];
		}
	}
	
	cout << max+1;
	
	return 0;
}

따라서 답은 4

라고 생각했지만(기존의 1탄은 이런방식으로 풀림),

N의 크기가 100만이 되어서 시간초과가 발생한다

 

[문제풀이]

이제부터 벡터의 가장 끝 원소가 기준값이 될것이다.

예제에서 주어진 값은 10 20 10 30 20 50 이다

1. 먼저 벡터에 10을 push해준다 x = 10
2. cursor 는 다음 타자인 20에 간다. 벡터에 있는 마지막 원소는 10이므로 20이 크니까 또 벡터에 push_back해준다
3. cusor = 10이 되고, 벡터 마지막 원소는 20이므로 cursor가 더 값이 작으므로 lower_bound를 돌려서 하한값을 찾고 그 위치에 cursor값을 넣는다
4. 반복!

**lower_bound의 사용법 : (dp.begin(), dp.end(), cursor) → 벡터의 첫 iterator과 마지막 iterator 중에서 cursor 이상의 값을 가지는 iterator를 반환한다.

단, 이분탐색으로 이루어지기 떄문에 항상 정렬되어 있어야 한다고 한다.

 

[코드]

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

int asize;//수열의 크기
int cursor;

int main() {
	
	cin >> asize;
	
	vector<int> dp;

	for(int i = 0; i < asize; i++){
		cin >> cursor;
		if(dp.empty() || dp.back() < cursor)
			dp.push_back(cursor);
		else{
			auto iter = lower_bound(dp.begin(), dp.end(), cursor);
			*iter = cursor; //iter가 해당 벡터의 위치를 가리키기 때문에 cursor의 값을 iter가 가리키는 벡터 위치에 저장하도록
		}
	}
	
	cout << dp.size();
	
	return 0;
}