백준 14003 가장 긴 증가하는 부분 수열 5 (c++) : 피너클

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

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

부분 수열의 길이를 구하는데 이진탐색을 사용할 것이고 부분 수열을 구하는데 백트래킹을 사용할것이다.

int n;
int arr[1000001];
int back[1000001];
vector<int> v;
vector<int>::iterator it;

사용할 변수다.

arr은 입력받을때, back은 백트래킹할때 v, it은 부분 수열을 구할 때 사용할 것이다.

cin >> n;
int idx = 1;

n을 입력받는다. idx는 값의 순서를 의미한다.

idx는 백트래킹에 사용할 것이다. 만약 back[3] == 1이라면 arr[3]이 부분수열에서 1번째에 사용됬다는것이다.

 

예제를 이용해 기본 작동방법을 설명하겠다.

10 20 10 30 20 50 이 값들을 순서대로 입력받을 것이다.

현재 v에는 아무런 값도 들어있지 않다.

10

만약 v에 아무런 값도 들어있지 않다면 v에 값을 집어넣고

10

20

v의 마지막 값보다 현재 입력받는 값이 더 크다면 v에 값을 집어넣는다.

만약 마지막 값보다 더 작은 값이 입력받는다면 v사이에 끼워넣어햐한다.

현재 10을 입력받았다. 마지막 값이 20이니 v사이에 끼워넣어야한다. 이때 이진 탐색을 이용할것이다.

이진 탐색을 이용해 10이 들어갈수있는 위치를 찾는다. 현재는 0번째에 들어갈 수 있다.

10

20

v에는 원래 있던 10이 아닌 새로 들어온 10이 들어가게된다. 이를 코딩으로 적으면 된다.

for (int i = 0; i < n; i++) {
	cin >> arr[i];
	if (v.empty()) {
		v.push_back(arr[i]);
		back[i] = idx++;
	}

값을 입력받고

v가 비어있다면 바로 arr[i]를 넣고 back[i]에 idx값을 넣는다.

예제를 예로 든다면 v에 10이 들어가고 back[0] = 1이 된것이다. back[0]이 1이니 arr[0]은 첫번째라는 뜻이다.

	else if (v[v.size() - 1] < arr[i]) {
		v.push_back(arr[i]);
		back[i] = idx++;
	}

만약 v의 마지막 값보다 입력받은 값이 크다면 위와 똑같이 하면 된다.

idx++를 하는 이유는 다음 들어오는 값은 지금 들어온 값의 다음 순서여야 하기 때문이다.

	else {
		it = lower_bound(v.begin(), v.end(), arr[i]);
		v[it - v.begin()] = arr[i];
		back[i] = (it - v.begin() + 1);
	}
}

둘 다 아니라면 중간에 값을 끼워넣어야 한다.

lower_bound를 이용해 끼워넣을 위치를 정한다.

lower_bound는 이진탐색 변수로 <algorithm>에 들어있다. 찾는 값 이상의 값을 가진 위치를 반환한다.

10, 20, 30, 40, 50에서 30을 찾는다면 30의 값을 가진 2번째 위치가 반환될 것이고

10, 20, 30, 40, 50에서 25를 찾는다면 25 이상의 값을 가진 30의 위치인 2번째가 반환될것이다.

it에는 v에서 arr[i]값 이상의 위치가 반환된다. it - v.begin()을 해야 일반적인 변수 값으로 사용할수있다.

v[it - v.begin()]을 arr[i]로 바꿔주고 back[i]는 arr[i]가 들어간 위치 + 1의 값을 넣어준다. (배열은 0부터 시작하니)

cout << v.size() << endl;
backtrack(v.size(), n - 1);

그후 v의 사이즈를 출력하고 backtrack을 하면 된다.

예제를 돌렸을때 back에는 아래와 같이 값이 들어가있다.

1

2

1

3

2

4

각각이 v에서 어디서 위치해 있었는지를 나타낸다. 이를 뒤에서 부터 확인할것이다. 그래서 '백'트래킹이다.

현재 v의 사이즈는 4이니 idx가 4인 놈이 마지막이다.

void backtrack(int num, int idx) {
	if (num == 0) return;
	if (back[idx] == num) {
		backtrack(num - 1, idx - 1);
		cout << arr[idx] << ' ';
	}
	else backtrack(num, idx - 1);
}

backtrack은 (출력해야 하는 idx, 현재 위치)를 전달받는다.

만약 출력해야하는 idx가 0이라면 바로 함수를 종료한다.

만약 back[현재 위치]가 출력해야하는 idx와 같다면 

backtrack(num-1, idx-1)를 한뒤 arr[idx]를 출력한다. 이래야 순서대로 나온다.

안그러면 10, 20, 30, 40이 출력되야 하는 상황에서 40, 30, 20, 10이 출력된다.

만약 back[현재 위치]가 출력해야하는 idx와 다르다면 backtrack(num, idx - 1)을 한다.

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

int n;
int arr[1000001];
int back[1000001];
vector<int> v;
vector<int>::iterator it;

void backtrack(int num, int idx) {
	if (num == 0) return;
	if (back[idx] == num) {
		backtrack(num - 1, idx - 1);
		cout << arr[idx] << ' ';
	}
	else backtrack(num, idx - 1);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	int idx = 1;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (v.empty()) {
			v.push_back(arr[i]);
			back[i] = idx++;
		}
		else if (v[v.size() - 1] < arr[i]) {
			v.push_back(arr[i]);
			back[i] = idx++;
		}
		else {
			it = lower_bound(v.begin(), v.end(), arr[i]);
			v[it - v.begin()] = arr[i];
			back[i] = (it - v.begin() + 1);
		}
	}
	cout << v.size() << endl;
	backtrack(v.size(), n - 1);
}

전체코드다.