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

 

 

 

<코드>

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

#define MOD 1000000007

int N, LIS_len;
int A[1000001], dp[1000001], LIS[1000001];
vector<long long> num[1000001], sum[1000001];

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

	// 수열 입력받기
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> A[i];

	// LIS 길이 구하기
	for (int i = 0; i < N; i++)
	{
		int idx = lower_bound(LIS, LIS + LIS_len, A[i]) - LIS;
		LIS[idx] = A[i];
		dp[i] = idx + 1;
		LIS_len = max(LIS_len, dp[i]);
	}

	cout << LIS_len << " ";

	for (int i = 1; i <= LIS_len; i++)
		sum[i].push_back(0);

	for (int i = N - 1; i >= 0; i--)
	{
		int j = 1;
		int len = dp[i]; // LIS 길이

		if (len < LIS_len)
		{
			int idx = upper_bound(num[len + 1].begin(), num[len + 1].end(), A[i]) - num[len + 1].begin();
			j = sum[len + 1].back() - sum[len + 1][idx];
		}
		num[len].push_back(A[i]);
		sum[len].push_back((j + sum[len].back()) % MOD);
	}
	
	cout << (sum[1].back() + MOD) % MOD << '\n';

	/* 출력부
	for (int i = 0; i < N; i++)
		cout << "A[" << i << "] : " << A[i] << '\n';
	cout << '\n';

	for (int i = 0; i < N; i++)
		cout << "dp[" << i << "] : " << dp[i] << '\n';
	cout << '\n';

	for (int i = 0; i < LIS_len; i++)
		cout << "LIS[" << i << "] : " << LIS[i] << '\n';
	cout << '\n';

	for (int i = 1; i <= LIS_len; i++)
	{
		cout << "num[" << i << "] : ";
		for (int j = 0; j < num[i].size(); j++)
			cout << num[i][j] << " ";
		cout << '\n';
	}
	cout << '\n';

	for (int i = 1; i <= LIS_len; i++)
	{
		cout << "sum[" << i << "] : ";
		for (int j = 0; j < sum[i].size(); j++)
			cout << sum[i][j] << " ";
		cout << '\n';
	}
	*/
}

 

풀이 방법

 

A[i] : 수열

dp[i] : i번째 까지의 LIS 길이

LIS[i] : LIS 길이를 구하기 위해 사용되는 배열

num[i] : LIS길이가 i인 원소들을 담는 벡터

sum[i] : LIS의 개수를 세기 위해 사용되는 벡터

 

예제입력1 출력 결과

 

예제입력2 출력 결과

 

예제입력3 출력 결과

 

 

 

www.acmicpc.net/problem/17411

17411번: 가장 긴 증가하는 부분 수열 6