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

문제 링크 => 14002번: 가장 긴 증가하는 부분 수열 4 (acmicpc.net)

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

---

다이나믹 프로그래밍 문제 + 약간의 생각을 더 해서 풀어야하는 문제이다.

 

참고로 이문제는 N=1000 밖에 안되기 때문에, 이분탐색을 사용하지 않고 다이나믹 프로그래밍으로 해결이 가능하다.

 

그러나 문제는 가장 긴 증가하는 부분 수열을 특정지어서 값을 표현하는게 생각보다 쉽지는 않았던거 같다.

 

이 문제를 해결하기 위해서 vector<int> v를 선언하였고 가장 큰 길이가 되도록 하는 배열의 index를 하나 잡아서 1씩 작아지면서 동시에 길이 또한 1씩 작아지는지를 동시에 체크하여 vector 에다가 배열 값을 차례로 push하는 방식으로 접근했다.

 

예제를 통해 위 방법을 간단하게 살펴보도록 한다.

 

6

10 20 10 30 20 50

 

이때 길이는 [ 1, 2, 1, 3, 2, 4 ] 이다. (인덱스는 0, 1, 2, 3, 4, 5)

 

이때 다이나믹 프로그래밍을 거치면서 길이가 더 큰 인덱스를 그 이전의 길이가 되도록 하는 인덱스를 이어주도록 하였다. ( 1 => 0, 3 => 1, 4 => 2, 4 => 1, 5 => 3 )

 

그 후에 가장 길이가 긴 인덱스 5를 기준으로 잡고 이어지는 부분이 없을때까지 다음 과정을 반복한다.

 

(i) 5일때 => (arr[3] < arr[5]) && dp[3] + 1 == dp[5] 를 만족하므로 3을 기준으로 잡는다.

 

(ii) 3일때 => (arr[1] < arr[3]) && dp[1] + 1 == dp[3] 를 만족하므로 1을 기준으로 잡는다.

 

(iii) 1일때 => (arr[0] < arr[1]) && dp[0] + 1 == dp[1] 를 만족하므로 0을 기준으로 잡는다.

 

마지막으로 0일때 인덱스 0의 이전 길이가 되도록 하는 인덱스가 없으므로 이 과정을 마친다.

 

벡터 v에 저장된 해당 인덱스의 배열값들을 역순으로 출력하게 되면 최종 정답이 된다.

 

---

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

int arr[1000];
int dp[1000];
vector<int> v[1001];

void solve(int n) {
	int res = 0, tmp=0;
	
	for (int i = 0; i < n; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
				dp[i] = dp[j] + 1;
				v[i].push_back(j);
			}
		}
		res = max(res, dp[i]);
		if (res == dp[i]) tmp = i;
	}
	cout << res << endl;

	vector<int> res_V;
	res_V.push_back(arr[tmp]);
	while (1) {
		if (v[tmp].size() == 0) break;
		int minNum = 1001;
		for (int i = 0; i < v[tmp].size(); i++) {
			int next = v[tmp][i];
			if (next < tmp && dp[next]+1==dp[tmp]) {
				minNum = next;
			}
		}
		tmp = minNum;
		res_V.push_back(arr[tmp]);
	}

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

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

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

	solve(n);

	return 0;
}