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

안녕하세요~

​

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

 

www.acmicpc.net/problem/12738

12738번: 가장 긴 증가하는 부분 수열 3

 

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

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

​

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

 

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

예제 입력 1 

6 10 20 10 30 20 50

예제 출력 1 

4

 

정답 코드 

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

int N;
int A[1000000];
vector<int> list;
void solve()
{
	list.push_back(A[0]);
	for (int i = 1; i < N; i++)
	{
		//마지막에 있는 값이 다음에 오는 값보다 크면 뒤에 넣는다.
		if (list[list.size() - 1] < A[i])
		{
			list.push_back(A[i]);
		}
		else
		{
			int start = 0;
			int end = list.size() - 1;
			int target = A[i];
			while (start <= end)
			{
				int mid = (start + end) / 2;
				if (list[mid] >= target)
				{
					end = mid - 1;
				}
				else
				{
					start = mid + 1;
				}
			}
			list[start] = target;
		}
	}
	cout << list.size() << 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();
}