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

문제 링크: https://www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

1. 주의할 점

- Arr[] 배열을 Long Long 타입으로 받는다

- DP[] 배열에 가장 긴 증가하는 부분 수열이 저장되어 있는 것이 아니다

 

2. 구현

- 모든 수를 Arr[]배열에 입력받고, Dp[0]=Arr[0], Idx=0, Ans[0].idx=0, Ans[0].val=Arr[0]으로 초기화 하고 시작한다

- For문을 1~Num-1까지 돌리며 Arr[i]>Dp[idx]를 만족하면 Dp[++idx] = Arr[i]를 하고 Ans[i].idx=idx, Ans[i].val=Arr[i]로 설정한다

- Arr[i] <= Dp[idx]인 경우, Arr[i]가 들어갈 곳을 Bianry_search()함수를 통해 찾은 후, 넣는다. 그리고 Ans[i].idx = 이분탐색의 Return idx값을 넣고, Ans[i].val = Arr[i]를 넣는다

- For문을 Num-1~0까지 하면서 Ans[i].idx와 T(초기값은 Idx)값이 같다면 V 벡터에 넣고 T--한다

- V 벡터를 역순으로 출력한다

 

#include <iostream>
#include <vector>
using namespace std;
struct info {
	long long idx, val;
};
info ans[1000000];
long long arr[1000000], dp[1000000], idx = 0, num;

long long binary_search(long long val) {
	long long l = 0, r = idx, mid, result = idx;
	while (l <= r) {
		mid = l + (r - l) / 2;
		if (dp[mid] >= val) {
			result = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	return result;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> num;
	for (int i = 0; i < num; i++)
		cin >> arr[i];
	dp[0] = arr[0];
	ans[0].idx = 0;
	ans[0].val = arr[0];
	for (int i = 1; i < num; i++) {
		if (dp[idx] < arr[i]) {
			dp[++idx] = arr[i];
			ans[i].idx = idx;
			ans[i].val = arr[i];
		}
		else {
			long long val = binary_search(arr[i]);
			dp[val] = arr[i];
			ans[i].idx = val;
			ans[i].val = arr[i];
		}
	}
	cout << idx + 1 << '\n';
	long long t = idx;
	vector<long long> v;
	for (int i = num - 1; i >= 0; i--) {
		if (ans[i].idx == t) {
			v.push_back(ans[i].val);
			t--;
		}
	}
	for (int i = v.size() - 1; i >= 0; i--)
		cout << v[i] << " ";
	system("pause");
	return 0;
}