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

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

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

난이도: solved.ac 골드 4

 

접근 방법

일반적인 dp를 이용한 N^2짜리 LIS 풀이로 가장 긴 부분 수열의 길이를 구하고

추가적인 코드를 통해 O(N)에 경로를 추적할 수 있다.

 

일단 LIS의 길이를 구하는 for문을 마치고 나면 len[i]에는 A[i]를 부분 수열의 마지막 원소로 썼을 때의 LIS 길이가 저장되게 된다.

따라서 경로를 구하려면 가장 len 값이 큰 원소부터 시작해 왼쪽 방향으로 len 값이 1씩 작은 곳을 찾아주면 된다.

그리고 여기에 해당 A 값이 더 작아야 한다는 조건을 추가하면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, i, j;
	int A[1000], len[1000], ans[1000];
	cin >> N;
	for (i = 0; i < N; i++)
		cin >> A[i];
	// LIS 구하기
	for (i = 0; i < N; i++) {
		len[i] = 1;
		for (j = 0; j < i; j++) {
			if (A[i] > A[j])
				len[i] = max(len[i], len[j] + 1);
		}
	}
	// 길이가 가장 긴 곳의 위치 찾기
	int maxlen = 0, maxidx;
	for (i = 0; i < N; i++)
		if (len[i] > maxlen) {
			maxlen = len[i];
			maxidx = i;
		}
	// 경로 추적
	ans[0] = A[maxidx];
	int l = maxlen - 1;
	for (i = maxidx - 1, j = 0; i >= 0; i--) {
		if (len[i] == l && A[i] < ans[j]) {
			ans[++j] = A[i];
			l--;
		}
	}
	cout << maxlen << "\n";
	for (i = maxlen - 1; i >= 0; i--)
		cout << ans[i] << ' ';
}

 

성능

코드 제출 결과