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

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

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

문제를 풀기전 이전에 풀었던 11053번 문제를 다시 살펴보자.

 

https://dwshin-dev.tistory.com/48

[백준 C++] 11053번: 가장 긴 증가하는 부분 수열

 

이 문제에서는 단순하게 가장 긴 증가하는 부분 수열의 길이만을 출력한다. 따라서 dp[i]값 중 가장 큰 수를 구하여 출력하면 되는 문제였다.

 

하지만 이번 문제에서는 그 수열까지 출력을 원하고 있다. 따라서 그 수열까지 저장 할 수 있는 배열을 지정해주어 같이 출력해 주면 된다 생각하고 문제를 풀어보았다. 그 배열은 b[i]이다.

 

하지만 dp[n]까지 구하고 나서야 최종적인 배열을 구할 수 있고 그러한 수열이 여러가지라고 한다면 아무거나 출력하므로 일단 가장 dp[i]가 가장 큰값을 구한다.

 

또한 그때의 i값을 cnt에 저장해놓고 b[cnt]에 a[i]값을 넣어준다. (마지막 배열 숫자값이므로)

 

그 cnt부터 1까지 천천히 내려가며 해당하는 수가 있는지 찾고 그 수를 새롭게 저장할 수 있는 배열에 넣어주자.(즉 그 다음수는 b[cnt-1]에 저장되며 마지막이 b[1]이 될때까지 반복한다.)

 

#include <iostream>
#include <algorithm>
using namespace std;
int a[1001] = { 0, };
int b[1001] = { 0, };
int dp[1001] = { 0, };
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
 
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
 
	int ans = 0, cnt = 0;
 
	for (int i = 1; i <= n; i++) {
		dp[i] = 1;
		for (int j = i - 1; j >= 1; j--) {
			if (a[i] > a[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		if (ans < dp[i]) {
			ans = dp[i];
			cnt = i;
		}
	}
 
	b[ans] = a[cnt];
	int l = ans - 1;
	for (int i = cnt - 1, j = ans; i >= 0; i--) {
		if (dp[i] == l && a[i] < b[j]) {
			b[--j] = a[i];
			l--;
		}
	}
 
	cout << ans << '\n';
	for (int i = 1; i <= ans; i++)
		cout << b[i] << ' ';
 
 
 
	
	return 0;
}

 

생각보다 쉽게 풀지는 못했던 문제.. 간단하게 배열을 저장할 수 있을 줄 알았지만 생각해야될것이 많았다.

 

그래도 내 방식대로 풀어서 기분이 좋았다.

 

큐에 배열값을 넣어 출력하는 방식도 고려해볼 수 있을것같다.