[백준OJ] 14002번 가장 긴 증가하는 부분 수열 4 , 14003번 가장 긴 증가하는 부분 수열 5

www.acmicpc.net/problem/14002

www.acmicpc.net/problem/14003

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

14002번: 가장 긴 증가하는 부분 수열 4

---

 

-풀이-

가장 긴 증가하는 부분수열 알고리즘을 이용했다. 

하지만 여기선 증가하는 부분수열중 하나를 출력까지 해야한다.

따라서 vector<pair<int,int>> trace를 선언해서 trace[i].first= i번째 원소는 증가하는 부분수열의 몇번째에 위치하는지, trace[i].second = i번째 원소가 무엇인지 기록을 해나간다.

 

사이트의 입력 예시를 들면

6

10 20 10 30 20 50

 

증가하는 부분수열을 v라고 하면

10은 v의 0번째 인덱스에 위치하면되므로 {0,10}으로 기록, 20은 v의 1번째 인덱스에 위치하면되므로 {1,20}으로 기록. 다음 10은 v의 0번째 인덱스에 위치할 수 있으므로 {0,10}으로 기록, 30은 v의 2번째 인덱스에 위치할 수 있으므로 {2,30}으로 기록, 20은 {1,20} , 50은 {3,50} 으로 기록 할 수 있다. 

 

기록을 해둔뒤, trace의 끝부분부터 조사를 해가며 , v의 마지막 인덱스~0 까지 만나는 순서대로 result에 넣어놓고, 거꾸로 출력을 해주면된다.

 

-시간 복잡도-

가장 긴 증가하는 부분수열을 구하는 부분은 전체 N을 돌며 각각 이분탐색을 하므로 O(N log N) 이 된다.

나머지 아래 로직들은 O(N log N)보다작으므로 시간복잡도는 O(N log N)이 된다.

 

-코드-

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int n;
vector<int> v,result;
vector<pair<int, int>> trace;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int data;
		cin >> data;
		if (v.empty() || v.back() < data) {
			trace.push_back({ v.size(),data });
			v.push_back(data);
		}
		else{
			int ind = lower_bound(v.begin(), v.end(), data) - v.begin();
			v[ind] = data;
			trace.push_back({ ind,data });
		}
	}

	int cnt = v.size() - 1;
	cout << v.size() << "\n";
	for (int i = n - 1;i>=0 ; i--) {
		if (trace[i].first == cnt) {
			result.push_back(trace[i].second);
			cnt--;
		}
	}
	for (int i = result.size() - 1; i >= 0; i--) {
		cout << result[i] << " ";
	}

}