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

문제 요약

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

문제 분류

• 다이나믹 프로그래밍

문제 풀이

우선 0~i번째까지의 가장 긴 증가하는 부분 수열(이하 LIS)의 최대 크기를 dp[]로 정하여 구축한다. r은 0~i사이의 dp[]중 최대값이며, ri는 그 위치이다. 이때 dp[i]는 ary[i]를 반드시 포함하므로 이전 값 ary[i - 1]보다 크다면 이전 값에 1을 합하고, 그렇지 않으면 다시 자신부터 세므로 1로 둔다.

이렇게 dp[]를 만들어서 그 최댓값인 r을 구하였으므로, 이젠 역추적하여 그 원소를 구해야한다. 여기서 선별할 ary[]의 범위는 0~ri가 될 것이며, ri번째 원소는 반드시 포함할 것이다.

이어서 정답을 출력할 vector에 dp[j] == r - 1 && ary[j] < ary[i]인 ary[j]를 추가하고, i를 j로 옮긴다. 최대 LIS의 크기 r의 크기도 1줄인다.

그렇게 r의 크기가 1이 되면 for문을 나와서 vector의 원소를 역순으로 출력한다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, ary[1001], dp[1001];

int main()
{
	int r = 1, ri = 0;
	vector<int> v;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", ary + i);

	dp[0] = 1;
	for (int i = 1; i < n; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (ary[j] < ary[i]) {
				dp[i] = max(dp[i], dp[j] + 1);
				if (r < dp[i]) {
					r = dp[i];
					ri = i;
				}
			}
		}
	}
	printf("%d\n", r);
	v.push_back(ary[ri]);
	for (int i = ri; i > 0;) {
		for (int j = i - 1; j >= 0; j--) {
			if (dp[j] == r - 1 && ary[j] < ary[i]) {
				i = j;
				r--;
				v.push_back(ary[j]);
				break;
			}
		}
		if (r == 1) break;
	}
	for (auto it = v.rbegin(); it < v.rend(); it++)
		printf("%d ", *it);

	return 0;
}