[동적 계획법과 최단거리 역추적 단계] 백준 14003번 가장 긴 증가하는 부분 수열 5

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

 

 

같은 이분탐색이지만, 기존은 길이만 물어봤다면 이번엔 그 최장 수열의 값을 함께 구해야 함.

그런데 갱신이 들어간 vector를 그대로 출력하면 틀린다.

그 이유는 1,5,10,4 과 같은 경우 해당 로직에서 1,4,10이 되어버리는데 길이는 정답이지만 4는 사실 10보다 뒤에 있으므로 연속되는 수열이 안됨.

 

증가하는 수열에서 순서대로 출력하기

값이 vector의 어느 인덱스에 위치하는지 기록한다.

그리고 들어온 수의 인덱스를 역행하면서 현재 시점 벡터의 가장 마지막 인덱스인 수를 스택에 저장하고 벡터의 길이를 하나 감소시킨다.

그러면 수열의 마지막 값이 되는 수부터 하나씩 스택에 들어오고 스택은 LIFO이므로 자동 리버스되서 작은 수부터 출력가능. 

 

 

#include <iostream>
#include <vector>
#include<string.h>
#include<queue>
#include <string>
#include<stack>
#include<cmath>
#include <map>
#include<algorithm>
using namespace std;
vector<int> vec;
int order[1000000];
int arr[1000000];
int lower(int start, int end, int n)
{
	int ans = 0;
	while (start <= end)
	{
		int mid = (start + end) / 2;
		if (vec[mid] >= n)
		{
			ans = mid;
			end = mid - 1;
		}
		else
		{
			start = mid + 1;
		}
	}
	return ans;
}


int main() {
	int N;
	cin >> N;
	
	vec.push_back(-1000000001);

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
		if (vec.back() < arr[i])
		{
			vec.push_back(arr[i]);
			order[i] = vec.size() - 1;
		}
		else
		{
			int idx = lower(0, vec.size(), arr[i]);
			vec[idx] = arr[i];
			order[i] = idx;
		}
	}
	printf("%d\n", vec.size() - 1);
	stack<int> sta;
	int len = vec.size() - 1;
	for (int i = N - 1; i >= 0; i--)
	{
		if (len == 0)
		{
			break;
		}
		if (order[i] == len)
		{
			sta.push(arr[i]);
			len--;
		}
	}
	while (!sta.empty())
	{
		printf("%d ", sta.top());
		sta.pop();
	}
	printf("\n");
}