[C++]백준 - 12015번 문제

12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net)

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

 

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

---

수열 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 ≤ Ai ≤ 1,000,000)

 

 

출력

---

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

 

 

---

 

생각해 볼 점

---

가장 긴 증가하는 수열은 11053번 문제와 동일합니다.

 

다만, 이번에는 이분 탐색을 이용해서 풀어야 합니다.

 

동적 프로그래밍을 이용하기에는 100만 만큼의 배열을 써야하므로, 이번에는 사용할 수 없습니다.

 

[최장 증가 수열] LIS(Longest Increasing Subsequence) (tistory.com)

[최장 증가 수열] LIS(Longest Increasing Subsequence)

 

알고리즘은 위의 사이트를 참고하여 코딩하였습니다.

 

코드

---

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

int main() 
{
	int N;
	scanf("%d", &N);
	
	vector<int> seq, sol;
	for(int i = 0; i < N; i++)
	{
	    int input;
	    scanf("%d", &input);
	    seq.push_back(input);
	}
	
	sol.push_back(seq[0]);
	int size = 1;
	for(int i = 1; i < N; i++)
	{
	    if(sol.back() < seq[i]) 
	    {
	        sol.push_back(seq[i]);
	        size++;
	    }
	    else
	    {
	        //Lower Bound 알고리즘, 이분탐색
	        int left = 0, right = size;
	        while(left < right)
        	{
        	    int mid = (left + right) / 2;
        	    if(sol[mid] < seq[i]) left = mid + 1;
        	    else right = mid;
        	}
        	sol[left] = seq[i];
	    }
	}
	
	cout << size;
	return 0;
}

 

그 외

---

이해하면 간단하지만, 혼자서는 생각해내지 못한 풀이이기 때문에, 아쉽습니다.

어떻게 이런 풀이를 떠올릴 수 있을까요?