[백준 BOJ][C++]14002번 가장 긴 증가하는 부분 수열의 길이4 풀이: DP

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

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

 

 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. 

 

 dp를 구조체를 이용하여 정의하였는데요, 구조체 멤버로 정수 n과 벡터 seq가 있습니다. dp[i]일때 n은 i번째 원소까지의 가장 긴 증가하는 부분 수열의 길이를 의미하고, seq는 그때의 원소 순서를 의미합니다. 

 

[풀이 과정]

1. 수열의 개수 n과 수열 arr을 입력

2. i번째 원소와 j(0<= j <= i-1)번째 원소들과 비교

3. j번째 원소 중 i번째 원소보다 작으면 dp[i].n과 dp[j].n+1 중 더 큰 값으로 dp[i].n값 갱신

4. 3. 과정에서 가장 큰 n값을 갖는 j를 maxidx로 갱신

5. dp[maxidx].seq를 dp[i].seq에 복사 후, dp[i].seq에 자기 자신(arr[i]) push

6. 가장 큰 n을 정답 ans에 저장, 이때의 index i를 idx에 저장 

 

 

 문제 예제 10 20 10 30 20 50 을 바탕으로 살펴볼까요?

 

먼저 arr[0]=10 부터 보겠습니다. 첫 번째 원소이니 당연히 부분 수열의 길이 n은 1, seq는 자기 자신 10 이겠지요

arr[i]	dp[i].n	dp[i].seq
10	1	10

 

arr[1]=20을 보겠습니다. arr[0]과 비교하면 arr[1]이 더 큽니다. 

이때 dp[1].n의 후보는 dp[1].n (1) vs dp[0].n + 1 (2) 이 됩니다. 더 큰 값인 2가 되고, dp[0].seq를 복사해오겠지요?

arr[i]	dp[i].n	dp[i].seq
10	1	10
20	2	10, 20

 

다음은 arr[2]=10입니다. arr[0], arr[1]보다 크지 않으므로 자동으로 본인만 부분 수열에 들어갑니다. 

arr[i]	dp[i].n	dp[i].seq
10	1	10
20	2	10, 20
10	1	10

 

arr[3]=30은 arr[0], arr[1], arr[2] 보다 모두 큽니다. 때문에 dp[3].n의 후보를 한 번 보겠습니다. 

dp[0].n+1 (2) vs dp[1].n+1 (3) vs dp[2].n+1 (2) 가 후보가 되겠습니다. 이때 가장큰 값이 3이고 이때의 index가 1입니다.

maxidx를 1로, dp[3].n을 3으로 갱신한 뒤 dp[3].seq에 dp[1].seq를 복사 후 자기 자신을 추가해봅시다.

arr[i]	dp[i].n	dp[i].seq
10	1	10
20	2	10, 20
10	1	10
30	3	10, 20, 30

 

 

 이 과정을 각 원소의 dp가 set 될 때마다 n과 seq가 어떻게 구성되는지 출력해봅시다. 

 

 풀이과정에 맞게 잘 출력되는 것을 볼 수 있습니다. 

 

 

다음은 전체 코드입니다. 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cmath>

using namespace std;

typedef struct info {
	int n;
	vector<int> seq;
};

vector<info> dp(1001, { 1, });
int arr[1001];

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int ans = 0, idx = 0;
	int n, maxidx;

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j]) {
				if (dp[i].n < dp[j].n + 1) {
					dp[i].n = dp[j].n + 1;
					maxidx = j;
				}
			}
		}

		if (dp[i].n <= 1) {
			dp[i].seq.push_back(arr[i]);
		}
		else {
			dp[i].seq = dp[maxidx].seq;
			dp[i].seq.push_back(arr[i]);
		}

		if (ans < dp[i].n) {
			ans = dp[i].n;
			idx = i;
		}
	}

	cout << ans << endl;

	for (int i = 0; i < dp[idx].seq.size(); i++)
		cout << dp[idx].seq[i] << " ";

	return 0;
}