[BOJ] 4198 - 열차정렬

[백준] 4198 - 열차정렬

접근

의식의 흐름은 대충 이러했다.

1. 이 문제 LIS아닌가?
2. 단순히 열차 순서에서 LIS로 뽑으면 최적이 나오지 않는다는 사실을 깨달음.
3. 그럼 열차를 정렬한 후 인덱스 기준으로 LIS를 뽑으면 되지 않나?
4. 어떠한 중간 지점을 최솟값이자 공통 값으로 갖는 두개의 LIS를 찾아내면 되겠다고 생각
   -> 그럼 각 중간 지점에 대해 일일이 LIS를 두 번 뽑아야 하는가? 시간복잡도가 O(N^2*logN)이 나오자 무언가 이상하다고 생각
   -> LIS 구현 과정에서 처음 시작부터 i번째까지 수행했을때 그것을 dp[i]에 저장할 수 있다는 사실을 깨달음
   -> 앞에서 뒤로 한 번, 뒤에서 앞으로 한 번 총 2번만 LIS를 뽑고 그것을 이용하자고 생각함

그리고 바로 구현으로 들어갔다.

구현

구현 과정에서 이 문제는 LIS가 아니라 LDS를 구해야 한다는 사실을 깨달았다.
기존 lower_bound는 오름차순으로 정렬된 배열에서 작동하기에 좌절하여 나름대로 자체 구현한 lower_bound를 사용하였고… 구현 오류 발생. 틀렸습니다..
질문검색 찬스를 사용해 첫번째 질문글에서 LDS의 구현은 LIS와 거의 비슷하다는 힌트를 봤다.(사실상 정답 스포.. 구현 방법까지 말씀해주셨기 때문에..)
그대로 구현하여 2트, 맞았습니다…

교훈

향후 목표라 하면, 두가지 정도가 있다.

1. LIS에 대해 다시 천천히 공부해보기.
2. lower_bound제대로 구현해보기.

소스코드

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> v;
int dp[2005], dpinv[2005];

int main(void) {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		v.push_back({ x, i });
	}
	sort(v.begin(), v.end());
	vector<int> tmp;
	for (int i = 0; i < n; i++) {
		if (tmp.empty() || tmp.back() < -v[i].second)
			tmp.push_back(-v[i].second);
		auto it = lower_bound(tmp.begin(), tmp.end(), -v[i].second);
		*it = -v[i].second;
		dp[i] = tmp.size();
	}
	tmp.clear();
	for (int i = n - 1; i >= 0; i--) {
		if (tmp.empty() || tmp.back() < -v[i].second)
			tmp.push_back(-v[i].second);
		auto it = lower_bound(tmp.begin(), tmp.end(), -v[i].second);
		*it = -v[i].second;
		dpinv[i] = tmp.size();
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans = max(dp[i] + dpinv[i + 1], ans);
	}
	printf("%d", ans);
	return 0;
}