[알고리즘] 백준 14002번: 가장 긴 증가하는 부분 수열 4 (C++), 앞으로는 temp를 잘 활용해보자

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

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

LIS 문제인 것을 떠나서 이건 monotonic stack으로 풀리지 않을까 싶어서 시도해봤지만 반례가 있었다.

 

[monotonic stack 시도]

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

int n;
int arr[1001] = { 0, };
int cache[1001] = { 0, };

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	stack<int> s;
	for (int i = n; i >= 1; i--) {
		if (!s.empty() && s.top() < arr[i]) {
			while (!s.empty() && s.top() < arr[i]) {
				s.pop();
			}
		}

		s.push(arr[i]);
	}

	cout << s.size() << '\n';
	while (!s.empty()) {
		cout << s.top() << ' ';
		s.pop();
	}

	return 0;
}

[Input]
7
1 2 3 4 10 8 9
[Output]
5
1 2 3 4 10
[Answer]
6
1 2 3 4 8 9

이런 일이 발생하는 이유는 monotonic stack에서 제일 하단에는 제일 큰 값이 들어가게끔 해놔서 그렇다. 그러다 보니 최장길이 증가 부분 수열을 발생시키는 8과 9는 10이 들어오면서 전부 pop이 되어버리기 때문이다.

 

monotonic stack과 LIS는 풍기는 뉘앙스만 비슷했을 뿐 방향성은 명확하게 달랐다.

---

솔루션 (temp의 활용)

기존의 LIS를 구하는 코드에서 어떤 것을 추가해야 할지 아니면 싹 다 들어내고 다른 방법을 모색해야 할지 고민에 빠졌었다. 싹 다 들어내는 것보다 기존의 코드를 활용하면 될 거 같은데 어떻게 활용해야 할지 방법을 못 찾았었다.

(+참고 https://cocoon1787.tistory.com/455)

 

참고한 포스팅에서는 temp변수를 사용하는데 사용한 방법이 참신했다.

 

[솔루션]

1. 최대 길이가 발생하는 길이 값을 temp에 저장한다, 인덱스 번호 또한 다른 변수에 저장한다.

2. 저장한 인덱스 번호부터 시작해서 길이 값이 temp인 경우 해당 arr값을 vector에 넣는다.

3. temp--;

4. 1~3 과정을 끝날 때까지 반복한다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int arr[1001] = { 0, };
int cache[1001] = { 0, };
int temp = 0;
int idx = 0;

int main() {
	int n;
	cin >> n;
	int value;
	for (int i = 1; i <= n; i++) {
		cin >> value;
		arr[i] = value;

		// LIS 길이 구하기
		cache[i] = 1;
		for (int j = i - 1; j >= 1; j--) {
			if (arr[j] < arr[i]) {
				cache[i] = max(cache[i], cache[j] + 1);
			}
		}

		if (cache[i] > temp) {
			temp = cache[i]; // 최대 길이 저장
			idx = i; // 최대 길이가 발생하는 인덱스 번호
		}
	}

	cout << temp << '\n';
	
    //이게 핵심
	vector<int> result;
	for (int i = idx; i >= 1; i--) {
		if (cache[i] == temp) {
			temp--; // << 어떻게 이런 생각을
			result.push_back(arr[i]);
		}
	}

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

	return 0;
}

---

느낀 점

temp 변수의 활용도와 temp변수를 어떻게 활용할 것인지 더 파고들어야 한다.

무조건 업 솔빙.