[BOJ/Platinum 5] 백준 14003 가장 긴 증가하는 부분 수열 5(C++)

문제 링크

https://www.acmicpc.net/problem/14003

 

문제

수열 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
10 20 30 50

 

알고리즘 분류

• 다이나믹 프로그래밍
• 이분 탐색

 

풀이

가장 긴 증가하는 부분 수열의 길이뿐만 아니라 실제로 수열을 구해야 하므로, 역으로 앞의 숫자를 추적하는 알고리즘을 구현해야 한다.

DP 배열을 선언한다. DP 배열은 LIS의 끝 원소로 가능한 숫자들로 구성되어 있으며, 이는 실제로 LIS를 나타내는 것은 아니다.

Indices 배열은 DP를 구성하는 숫자들의 Index로 구성되어 있고, PrevIndices에는 현재 Index의 이전 Index를 기록한다.

이분 탐색을 활용해서 Numbers의 현재 숫자가 DP의 어느 위치에 들어가기에 적절한지를 구하고, 이전 Index도 기록해둔다.

마지막으로 끝 Index부터 시작해서 처음 Index가 나올 때까지 역추적하면서 LIS를 재구성한다. 역추적했기 때문에 reverse()로 반전시킨 배열이 우리가 찾는 LIS가 된다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N;
vector<int> Numbers;
vector<int> LIS;

void input() {
	cin >> N;
	Numbers.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> Numbers[i];
	}
}

vector<int> findLis() {
	vector<int> Result;
	vector<int> DP;
	vector<int> Indices;
	vector<int> PrevIndices(N, -1);

	for (int i = 0; i < N; i++) {
		auto it = lower_bound(DP.begin(), DP.end(), Numbers[i]);
		int Index = it - DP.begin();

		if (it == DP.end()) {
			DP.push_back(Numbers[i]);
			Indices.push_back(i);
		}
		else {
			*it = Numbers[i];
			Indices[Index] = i;
		}

		if (Index > 0) {
			PrevIndices[i] = Indices[Index - 1];
		}
	}

	int Current = Indices.back();
	while (Current != -1) {
		Result.push_back(Numbers[Current]);
		Current = PrevIndices[Current];
	};

	reverse(Result.begin(), Result.end());

	return Result;
}

void settings() {
	LIS = findLis();
}

void printAnswer() {
	cout << (int)LIS.size() << "\n";
	for (int i = 0; i < (int)LIS.size(); i++) {
		cout << LIS[i] << " ";
	}
	cout << "\n";
}

int main() {
    FASTIO

	input();
	settings();
    printAnswer();

    return 0;
}