[백준 알고리즘][C++] 이분 탐색(binary search) - 12015번 가장 긴 증가하는 부분 수열 2

안녕하세요~

​

이번시간에는 12015번 가장 긴 증가하는 부분 수열 2 문제를 풀어보려고 합니다.

 

www.acmicpc.net/problem/12015

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

명심하셔야 될 것은 일단 문제를 풀기 전에 코딩을 먼저 시작하지 마시고, 반드시 연습장으로 생각을 정리하고! 이 후에 생각이 맞는 것 같다고 확신이 되면 그 때 코딩을 시작하세요. 코드를 작성하면서 문제를 풀게되면 정리가 안된 상태기 때문에 코드 수정이 잦아지고, 정신이 없어지게 됩니다ㅠㅠ

그러니 반드시 노트에 어떻게 풀 것인지에 대한 정리를 다 하시고 코딩을 시작하시기 바랍니다!!

​

binary search 공부에 좋은 문제입니다.

#include <iostream>
using namespace std;

int N;
int A[1000001];
int list[1000001];
void binary_search(int start, int end, int target)
{
	while (start <= end)
	{
		int mid = (start + end) / 2;
		if (target <= list[mid])
		{
			end = mid - 1;
		}
		else
		{
			start = mid + 1;
		}
	}
	list[start] = target;
}
void solve()
{
	int list_pos = 0;
	list[0] = A[0];
	for (int i = 1; i < N; i++)
	{
		//list의 마지막 위치보다 A의 값이 크면 list의 마지막 위치에 추가
		if (list[list_pos] < A[i])
		{
			list_pos++;
			list[list_pos] = A[i];
		}
		//list의 마지막 위치보다 A 값이 작으면 list 안에 binary search로 찾아서 넣기
		else if (list[list_pos] > A[i])
		{
			binary_search(0, list_pos, A[i]);
		}
	}
	cout << list_pos+1 << endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	solve();
}