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

문제

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

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

---

문제 요약

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열과 그 길이를 출력한다.

 

ex) 수열 A = {10, 20, 10, 30, 20, 50} 인 경우, 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이다.

---

코드

#include<iostream>
#include<vector>

using namespace std;

int n;

vector<int> arr, v, index, res;

int binarySearch(int num) {
	int left = 0;
	int right = v.size() - 1;
	int ans;

	while (left <= right) {
		int mid = (left + right) / 2;

		if (v[mid] >= num) {
			right = mid - 1;
			ans = mid;
		}
		else {
			left = mid + 1;
		}
	}

	return ans;
}

int main() {
	// arr에 입력 받은 수열 정보 저장
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}

	// 초기값 삽입
	v.push_back(arr[0]); 
	index.push_back(0);

	// v,index 채우기
	for (int i = 1; i < n; i++) {
		if (arr[i] > v.back()) {
			index.push_back(v.size());
			v.push_back(arr[i]);
		}

		else {
			int idx = binarySearch(arr[i]); // arr[i] 보다 큰 수 중 가장 먼저 등장하는 수의 인덱스
			v[idx] = arr[i];
			index.push_back(idx);
		}
	}

	// 정답 출력
	cout << v.size() << "\n";

	int find_idx = v.size() - 1;
	for (int i = n - 1; i >= 0; i--) {
		if (index[i] != find_idx) continue;
		find_idx--;
		res.push_back(arr[i]);
	}

	for (int i = res.size() - 1; i >= 0; i--) {
		cout << res[i] << " ";
	}

	return 0;
}

---

코드 설명

 < vector >

arr: 입력 받은 수열 A를 저장하는 벡터

 

res: 가장 긴 증가하는 부분 수열을 거꾸로 저장할 벡터

+ 거꾸로 출력한다.

 

v: 가장 긴 증가하는 부분 수열의 길이와 같은 길이의 벡터 + 오름차순이 유지되며 수열 A의 모든 값이 v에 1번씩 저장된다.

 

index: arr[i]가 v에 저장되었던 위치 인덱스를 저장하는 벡터

 

< 순서 >1. 초기 값을 설정한다.

 

1 - 1. 초기에는 v가 비어있으므로 arr[0]을 그냥 삽입한다.

 

1 - 2. arr[0]이 v의 1번 인덱스에 삽입되었으므로 index[0]을 0으로 설정한다. (0 삽입)

 

2. 나머지 arr 요소들을 왼쪽부터 차례대로 체크하며 v에 삽입한다.

 

2 - 1. arr[i]가 v의 가장 큰 요소(가장 오른쪽에 있는 요소)보다 크면 그대로 v 뒤에 삽입하고, 그렇지 않다면 v에서 arr[i]보다 큰 요소 중 가장 작은 요소 (가장 왼쪽에 있는 요소)와 교체한다.+ arr[i]보다 큰 요소중 가장 작은 요소를 찾기 위해 이진 탐색을 사용한다. (lower_bound)

 

2 - 2. v에 들어간 위치를 index에 삽입한다.

 

3. 가장 긴 증가하는 부분 수열의 길이는 v의 길이가 된다.+ 그러나 v는 가장 긴 증가하는 부분 수열이 아니다.

 

4. 가장 긴 증가하는 부분 수열을 생성한다.

 

4 - 1. find_idx를 v의 마지막 인덱스 번호(가장 긴 증가하는 부분 수열의 마지막 인덱스 번호)로 설정하고, index의 요소를 오른쪽부터 차례대로 체크하여 find_idx와 같다면, arr[i]를 res에 저장하고, find_idx를 1 감소시킨다.+ 차례

 

5. res를 거꾸로 출력한다.

 

참고: https://yabmoons.tistory.com/561