[C/C++] 백준 12738번 - 가장 긴 증가하는 부분 수열 3 (LIS)

 

<코드>

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

int N, cnt;
int A[1000001], dp[1000001];
vector<int> v, ans;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> A[i];
		
	v.push_back(A[1]);

	for (int i = 2; i <= N; i++)
	{
		if (v[cnt] < A[i])
		{
			v.push_back(A[i]);
			cnt++;
			dp[i] = cnt;
		}
		else
		{
			int pos = lower_bound(v.begin(), v.end(), A[i]) - v.begin();
			v[pos] = A[i];
			dp[i] = pos;
		}
	}

	cout << cnt + 1;
	
}

 

풀이 방법

 

위의 풀이는 LIS의 길이는 구할 수는 있지만 LIS를 구할 수 없는 풀이이다. 

예를 들어

4
10 50 100 20

의 입력이 주어졌을 때 LIS의 길이는 3을 구할 수는 있지만

실제로 v벡터에 남아있는 값은 {10, 20, 100}이다. 길이만 구하면 되기에 이런 식으로 풀이를 하였다.

 

 

 

www.acmicpc.net/problem/12738

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