백준 14003 가장 긴 증가하는 부분 수열5

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

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

 

---

가장 긴 증가하는 부분 수열 3을 푼 이후라 어떻게 가장 긴 증가하는 부분수열의 길이를 구하는지는 알았다. 

 

하지만 정답인 부분수열을 어떻게 구해야하는가? 에 대해선

진짜

진짜 아무리 생각해도 모르겠어서 좀 컨닝을 했다.. 

 

트리에서 parent 를 구하기 위해 p배열을 트리의 크기만큼 생성하고 트리를 순회하면서 값을 갱신하는 경우에 p를 업데이트 시키려고 했는데 도저히 구해지지 않았다.

 

 

 

정답코드를 보니 내 생각보다 간단하게 구할 수 있었다...

 

p배열의 크기는 배열의 크기만큼으로 해주고
p의 인덱스는 정렬되지 않은 원본배열에서의 원소 인덱스를 의미한다.
p의 값은 해당 원소가 lis에서 몇번쨰 원소로 쓰이고 있는지를 저장한다.

 

 

예제의 경우를 예로 들면

원본 배열은

not sorted	1	2	3	4	5	6
	10	20	10	30	20	50

이다.

 

이 배열을 숫자의 크기가 점점 커지게, 같은 수의 경우 인덱스가 큰 것을 먼저 오게 정렬해준다. 

 

그러면 정렬된 배열은

sorted	1	2	3	4	5	6
	10	10	20	20	30	50

이다. 

 

세그먼트 트리에서 베열의 노드를 의미하는 단말노드들이 업데이트된다, n 단말 노드에 저장되는 값은 1 ~ n 사이 제일 긴 증가하는 부분 수열의 길이이다. 이 때 p배열을에  단말노드에 저장되는 값과 같은 값을 넣어주면 된다. 

 

즉 1 ~ n 인덱스 중 제일 긴 증가하는 부분수열의 길이는 n번 노드가 위치값과 같은 숫자이다. 

 

 

p배열은

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

 

이렇게 업데이트 된다.

 

 n=4 (가장 긴 부분수열의 길이)  

p배열의 끝부터 순회한다{

    p[i]==n 이라면{

       sorted[6]을 정답 배열에 저장하고

       n--;

    }

  i--;

}

이렇게 정답을 저장했다.

 

 

 

 

풀이 아이디어를 생각하지 못한게 아쉽긴하다...

문제의 풀이를 완벽하게 이해하지 못해서 코드도 깔끔하지 못한게 좀 답답하ㄷ ㅏ...

 

좀 더 깔끔하게 정리해서 다시 제출해봐야겠다.;;

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;
using ll = long long;
int st_size;
vector<int>p;
vector<pair<ll, int>>sorted;
vector<int>st;//세그먼트 트리 구간에서 lis길이 저장


bool cmp(pair<ll, int> a, pair<ll, int> b) {
	if (a.first == b.first) {
		return a.second > b.second;
	}
	else
		return a.first < b.first;
}
int lis(int l,int r) {
	int maxA = 0;

	l = l + st_size - 1;
	r = r + st_size - 1;
	int index = r;
	while (l <= r) {
		if (l == r) {
			if (maxA < st[l]) {
				maxA = st[l];
			}
			break;
		}
		if (l % 2 == 1) {
			if (maxA < st[l]) {
				maxA = st[l];

			}
			l++;
		}
		if (r % 2 == 0) {
			if (maxA < st[r]) {
				maxA = st[r];

			}
			r--;
		}
		if (l > r)
			break;
		l /= 2;
		r /= 2;
	}
	return maxA;
}
void makeTree() {
	for (int i = 0; i < sorted.size(); i++) {
		int index = sorted[i].second + st_size - 1;

		st[index] = lis(1, sorted[i].second) + 1;
		p[sorted[i].second] = st[index];

		while (index > 1) {
			index /= 2;
			if (st[index * 2] > st[index * 2 + 1]) {
				st[index] = st[index * 2];

			}
			else {
				st[index] = st[index * 2+1];

			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int s;//배열 사이즈
	cin >> s;
	st_size = s * 4;//트리에서 단말노드 시작 위치


	st.resize(st_size * 2);//세그먼트 트리 크기
	p.resize(s+1, 0);
	vector<int>notSorted(s + 1);
	sorted.resize(s + 1, pair<ll, int>{0, 0});

	sorted[0] = { 9000000000,0 };

	for (int i = 1; i <= s; i++) {
		cin >> sorted[i].first;
		sorted[i].second = i;
		notSorted[i]= sorted[i].first;
	}


	sort(sorted.begin(), sorted.end(), cmp);//배열 정렬

	makeTree();

	cout << st[1]<<"\n";

	int n = st[1];

	vector<int>answer;
	for (int i =p.size()-1; i >=1; i--) {
		if (p[i] == n) {
			answer.push_back( notSorted[i]);
			n--;
		}

	}
	while (!answer.empty()) {
		cout << answer.back()<<" ";
		answer.pop_back();
	}

	return 0;
}