[백준 14002] 가장 긴 증가하는 부분 수열 4 (C++)

문제 링크: https://www.acmicpc.net/problem/14002

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

1. 주의할 점

- DP처럼 진행한다

- 가장 긴 증가하는 부분 수열을 어떤 방식으로 담을 건지 생각한다

 

2. 구현

- 배열을 입력받으면서, Result[]배열도 초기화 작업을 한다

- i: 1~Num-1, j: 0~i-1까지 반복하면서 Arr[i]>Arr[j]를 만족한다면 Result 배열의 인자를 비교하여 이전보다 긴 수열이 가능하면 바꾸고, Arr[i]보다 작은 배열의 idx값을 pre_idx에 저장한다. 만약 길이가 같다면, pre_idx에 저장된 값과 비교하여 바꾸는 것이 더 작으면 바꾼다

- For문이 끝난 후, 가장 긴 수열의 idx값을 저장한다

- While문을 통해 idx의 값이 Result[idx].pre_idx와 같다면, 가장 긴 증가하는 부분 수열의 앞이므로 끝낸다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct info {
	int pre_idx, len;
};
int arr[1000], num, idx = 0, max_len = 1;
info result[1001];
vector<int> v;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> arr[i];
		result[i].len = 1;
		result[i].pre_idx = i;
	}
	
	for (int i = 1; i <= num; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j]) {
				if (result[i].len == result[j].len + 1 && arr[result[i].pre_idx]>arr[j]) {
					result[i].pre_idx = j;
				}
				else if (result[i].len < result[j].len + 1) {
					result[i].len = result[j].len + 1;
					result[i].pre_idx = j;
				}
			}
		}
	}
	for (int i = 1; i < num; i++) {
		if (result[i].len > max_len) {
			max_len = result[i].len;
			idx = i;
		}
	}
	while (1) {
		v.push_back(arr[idx]);
		if (idx == result[idx].pre_idx)
			break;
		idx = result[idx].pre_idx;
	}
	cout << v.size() << '\n';
	for (int i = v.size() - 1; i >= 0; i--)
		cout << v[i] << " ";
	system("pause");
	return 0;
}