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

링크

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

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

해설

12015 가장 긴 증가하는 부분 수열 2 와 상당히 유사합니다.

 

이 풀이는 12015 의 풀이내용을 제외한 수열을 찾는 방법에 대한 해설만 적혀있으므로 

12015 를 풀어보지 않았다면 위의 글을 먼저 읽고오시길 바랍니다.

 

 

12015 의 풀이대로 풀면 계속 수열을 덮어씌우는 방법으로 갯수를 늘려나가서

원래의 수열을 찾기는 쉽지 않습니다.

그러나 각 입력별로 몇번째 idx 자리에 들어갔는지를 알고있다면

현재 idx 에서 왼쪽으로 탐색하다가 처음으로 만나는 idx - 1 인 값은 현재값보다 반드시 작을 것 입니다.

이것을 이용하면 간단히 풀 수 있습니다.

 

알고리즘을 요약하자면

1. 입력을 받을 때 이 값의 idx 값 또한 저장해둔다.

2. idx 값을 저장해둔 배열을 뒤에서 부터 탐색하면서 idx, idx - 1, idx - 2, ... 인 값들을 스택에 차례로 저장

3. 스택에서 값을 차례로 빼내면 정답

 

백준의 예제를 예로 들어보겠습니다.

10 20 10 30 20 50 의 idx 값들은

10	20	10	30	20	50
1	2	1	3	2	4

위와 같이 나올 것 입니다.

그러면 알맞은 수열을 찾기위해 위의 알고리즘을 적용하면

 

6번째 idx = 4

idx = 4

같으므로 스택에 저장합니다. ( idx-- )

스택 : 50

 

5번째 idx = 2

idx = 3 다르므로 패스

스택 : 50

 

4번째 idx = 3

idx = 3

같으므로 스택에 저장합니다. ( idx-- )

스택 : 50 30

 

3번째 idx = 1

idx = 2 다르므로 패스

스택 : 50 30

 

2번째 idx = 2

idx = 2

같으므로 스택에 저장합니다. ( idx-- )

스택 : 50 30 20

 

1번째 idx = 1

idx = 1

같으므로 스택에 저장합니다. ( idx-- )

스택 : 50 30 20 10

 

스택을 뒤집으면 정답인 10 20 30 50 이 나오게됩니다.

 

아래 코드에 모두 구현되어있습니다.

 

코드

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

int N, IN[1000000], idx = 0, TABLE[1000000], STACK[1000001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	STACK[0] = -1000000001;
	for (int i = 0; i < N; ++i) {
		cin >> IN[i];
		if (IN[i] <= STACK[idx]) {
			int* bound = lower_bound(STACK, STACK + idx, IN[i]);
			*bound = IN[i];
			TABLE[i] = bound - STACK;
		}
		else {
			STACK[++idx] = IN[i];
			TABLE[i] = idx;
		}
	}

	cout << idx << "\n";

	int looper = N - 1;
	vector <int> stk;
	while (idx != 0) {
		if (TABLE[looper] == idx) {
			stk.push_back(IN[looper]);
			idx--;
		}
		looper--;
	}

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

	return 0;
}