[백준/c++] 14002번 - 가장 긴 증가하는 부분 수열 4

[ 참고 ]

 

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

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

를 먼저 풀면 좋은 문제이다.

 

 

[ 문제 ]

 

 

 

[ 구현 ]

 

N이 1000이므로 시간복잡도 O(N^2)의 이중 for문으로 풀었다.

 

if(arr[i] > arr[j])

     dp[i] = max(dp[i], dp[j] + 1);

 

의 점화식을 이용해 최대 길이를 구함과 동시에

record배열을 하나 더 만들어 dp[i]가 갱신될 때마다 record[i]의 값이 이전의 최댓값인 j를 가지도록 했다.

 

max가 되는 dp의 인덱스를 mx_idx에 저장하고

mx_idx에서부터 이전에 저장한 record 배열을 이용해 하나씩 풀어가며 stack에 저장.(순서를 뒤바꾸기 위해)

 

마지막으로 stack에서 하나씩 출력하고 pop하는식으로 구현했다.

 

 

[ 코드 ]

 

#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

int n;
int dp[1003];
int arr[1003];
int record[1003];
int ans = 0;

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

	cin >> n;

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

	if (n == 1) {
		cout << 1 << '\n';
		cout << arr[1];
		return 0;
	}

	int mx_idx = 1;

	for (int i = 1; i <= n; i++) {
		dp[i] = 1;
		for (int j = 1; j < i; j++) {
			if (arr[j] < arr[i]) {
				if (dp[i] < dp[j] + 1) {
					dp[i] = dp[j] + 1;
					record[i] = j;
				}
			}
			if (ans < dp[i]) {
			ans = dp[i];
			mx_idx = i;
			}
		}
	}

	cout << ans << '\n';
	stack<int> s;

	for (int i = 0; i < ans; i++) {
		s.push(arr[mx_idx]);
		mx_idx = record[mx_idx];
	}

	while (!s.empty()) {
		cout << s.top() << " ";
		s.pop();
	}


	return 0;
}

 

[ 마무리 및 느낀 점 ]

많이 지저분하지만 record 배열을 통해 최대 길이의 경우에 대해서만 stack에 push하고 싶다는 설계대로 구현을 성공한 것에 의의를 두고싶다.