[BOJ/Platinum 5] 백준 31503 DP (Large)(C++)

문제 링크

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

 

 

문제

이 문제는 DP (Small)과 문제의 수 제한, 질문의 수 제한, 문제의 난이도 제한이 다른 문제이다.

DP는 DYNAMIC Porani의 약자이다.

DYNAMIC한 포라니는 가능한 문제를 DYNAMIC하게 푸는 것을 좋아한다. DYNAMIC한 문제 풀이란 문제의 번호와 난이도가 모두 증가하도록 가능한 한 많이 푸는 것이다.

방학을 맞은 포라니는 알고리즘 능력 향상을 위해 선배로부터 추천 문제 셋을 받았다. 나태한 포라니는 모든 문제를 풀고 싶지 않다. 만약 선배로부터 어떤 문제를 풀라는 지시를 받았을 때, 그 문제를 포함하여 DYNAMIC하게 문제를 풀었을 경우 몇 문제를 풀어야 하는지 알려주자.

 

입력

첫 번째 줄에 문제의 수 N(1 ≤ N ≤ 300,000)과 쿼리의 수 Q(1 ≤ Q ≤ N)가 공백으로 구분되어 주어진다.

두 번째 줄에 문제의 난이도를 나타내는 음이 아닌 정수 Di(1 ≤ i ≤ N; 0 ≤ Di ≤ 3 × 10^8)가 문제 번호의 순서대로 공백으로 구분되어 주어진다. 문제 번호는 1부터 시작하는 연속된 양의 정수이다.

세 번째 줄부터 Q개의 줄에 걸쳐 선배가 풀라고 한 문제의 번호 Ai(1 ≤ i ≤ Q; 1 ≤ Ai ≤ N)가 주어진다. 쿼리로 주어지는 문제의 번호는 중복되지 않는다.

 

출력

 Q개의 줄에 걸쳐, i번째 줄에 i번째 선배의 지시에 따라 풀어야 하는 문제 수를 순서대로 출력한다.

 

예제 입력 1

6 6
1 2 3 4 3 2
1
2
3
4
5
6

예제 출력 1

4
4
4
4
3
2

 

알고리즘 분류

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

 

풀이

쿼리의 개수는 최대 300,000개까지이며, 따라서 300,000개의 LIS를 구하면 되나 싶지만 그렇게 된다면 O(n^2logn)만큼의 시간복잡도를 가지기 때문에 시간 초과가 발생할 것이다.

LIS를 2번만 구해서 O(nlogn)만큼의 시간복잡도로 해결하는 방법이 존재한다.

왼쪽에서부터 시작하는 LIS를 구하면서, 현재 인덱스까지 탐색했을 때 도출된 LIS의 길이를 기록해둔다.

오른쪽에서부터 시작하는 LIS를 구해야 하는데, 문제의 난이도만 거꾸로 반전시켜서 구하면 LIS를 구할 수가 없다. 따라서, 입력을 받으면서 미리 마이너스를 붙여 lower_bound로 이분 탐색으로 LIS를 구할 수 있도록 미리 반전된 문제 난이도 배열을 저장한다.

이제부터는 Q개의 주어진 문제 인덱스별로 해당 문제가 포함된 LIS를 구할 수 있다. 왼쪽 LIS의 현재 인덱스는 처음부터 현재 인덱스까지 나올 수 있는 LIS의 최대 길이이며, 오른쪽 LIS의 현재 인덱스는 현재 인덱스부터 끝 숫자까지 나올 수 있는 LIS의 최대 길이이다.

이 두 값을 더해주고, 현재 인덱스의 문제 난이도가 중복이 되므로 1을 뺀다. 그렇게 해서 구한 값이 쿼리문에 주어진 문제를 포함하는, DYNAMIC하게 문제를 풀었을 때의 문제 개수가 된다.

 

코드

#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, Q;
vector<int> Numbers, ReverseNumbers, Queries, LeftLisLengths, RightLisLengths;
vector<int> Answer;

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

vector<int> findLisLengths(bool isReversed) {
	vector<int> Result(N, 0);
	vector<int> Temp;
	vector<int> DP;

	if (isReversed) {
		Temp = ReverseNumbers;
		reverse(Temp.begin(), Temp.end());
	}
	else {
		Temp = Numbers;
	}

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

		if (IT == DP.end()) {
			DP.push_back(Temp[i]);
		}
		else {
			*IT = Temp[i];
		}
		Result[i] = Index + 1;
	}

	if (isReversed) {
		reverse(Result.begin(), Result.end());
	}

	return Result;
}

void settings() {
	LeftLisLengths = findLisLengths(false);
	RightLisLengths = findLisLengths(true);
	for (int i = 0; i < Q; i++) {
		int Length = LeftLisLengths[Queries[i] - 1] + RightLisLengths[Queries[i] - 1] - 1;
		Answer.push_back(Length);
	}
}

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

int main() {
    FASTIO

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

    return 0;
}