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

1. problem : 

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

 

 

2. solution 1: 

#include <bits/stdc++.h>
using namespace std;
const int nums = 1005;
int A; 
int a[nums]; 
int d[nums]; 
int pre[nums]; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> A; 
	for (int i = 1; i <= A; i++) cin >> a[i]; 

	for (int i = 1; i <= A; i++) {
		d[i] = 1; 
		pre[i] = -1;
		for (int j = 1; j < i; j++) {
			if (a[j] >= a[i]) continue;
			if (d[i] < d[j] + 1) {
				d[i] = d[j] + 1; 
				pre[i] = j;
			}
		}
	}
	int mx_idx = 1; 
	int mx_cnt = 1;
	for (int i = 1; i <= A; i++) {
		if (mx_cnt < d[i]) {
			mx_cnt = d[i]; 
			mx_idx = i;
		}
	}
	deque<int> dq; 
	dq.push_front(mx_idx); 
	cout << mx_cnt << '\n';
	while (pre[dq.front()] != -1) {
		dq.push_front(pre[dq.front()]);
	}
	for (int idx : dq) {
		cout << a[idx] << ' ';
	}
}

dp를 이용해 풀었다. 따라서, 세 가지 스텝으로 문제를 풀어나갔다. 

첫 번째, 테이블을 정의한다. d [i]는 i번째 인덱스를 포함했을 때 최장 길이를 저장한다. 

두 번째, 점화식을 작성한다. i전까지 loop를 돌며, d [i] < d [j] + 1을 만족한다면, d [i] = d [j] + 1이 된다. 만약에 그렇지 않다면, d [i] = 1이다. 

세 번째, 초기값을 설정한다. 초기값은 1로 했다. 그 이유는 각각의 수들은 자기 자신을 포함하니, 1이 돼야 한다. 

 

마지막으로 경로를 역추적하는 방법은 deque를 이용했다. pre라는 배열을 만들어, 이 배열에는 j값을 기록했다. 이 인덱스들을 deque에 담았고, 역추적을 했다.