C++ / 백준 / 14002 / 가장 긴 증가하는 부분 수열 4

문제

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

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

 

문제풀이

가장 긴 증가하는 부분 수열 다른 문제부터 풀면 편하다

해당 문제: https://www.acmicpc.net/problem/11053

해당 문제풀이: https://githubseob.tistory.com/17

 

예시를 푼 방법을 나타낸 표

현재 숫자가 n일 때 1부터 n-1까지 돌면서 최장 길이를 찾고 DP[n][0]에, n을 제외한 최장 길이의 끝 숫자를 DP[n][1]에 집어넣고 반복문이 종료되면 최장 길이를 찾고 스택에 집어넣으면서 후입 선출을 이용해서 풀었다.

 

	for (y = 0; y < N; ++y) {
		for (x = 0; x < y; ++x) {
			if (Arr[x] < Arr[y]) {
				if (DP[y][0] <= DP[x][0]) {
					DP[y][0] = DP[x][0] + 1;
					DP[y][1] = x;
				}
			}
		}
	}

현재 숫자가 y이면 x는 0부터 y-1까지 돌면서 입력받은 배열 값보다 작은 숫자들을 찾는다.

그중 현재 숫자보다 DP값이 큰 x값을 찾을 때마다 y의 DP값을 DP[x][0] +1로 바꾼고 그때의 x값을 DP[y][1]에 저장한다.

이러면 y일 때 가장 긴 부분 수열의 길이가 DP[y][0]에 저장되고, 바로 직전의 x값이 DP[y][1]에 저장된다.

 

	for (x = 0; x < N; ++x) {
		if (big < DP[x][0]) {
			big = DP[x][0];
			big_x = x;
		}
	}

DP[x][0]를 돌면서 가장 긴 부분 수열의 길이를 찾고 그때 x를 big_x에 저장한다.

 

	for (big; big > 0; --big) {
		seq.push(Arr[big_x]);
		big_x = DP[big_x][1];
	}
	while (!seq.empty()) {
		cout << seq.top() << " ";
		seq.pop();
	}

답은 작은 수부터 출력해야 하므로 후입 선출인 스택에 집어넣는다.

50을 집어넣고 DP[5][1]값인 3을 입력받는다.

DP[3][0] = 30을 집어넣고 1을 입력받는다. 이런 식으로 길이만큼 반복한다.

스택에 모든 값을 집어넣었으면 스택의 top부분을 빌 때까지 출력한다.

 

 

코드

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N = 0;
	int y = 0, x = 0;
	cin >> N;

	vector<int>Arr(N, 0);
	vector<vector<int>>DP(N, vector<int>(2, 1));
	stack<int>seq;
	
	for (x = 0; x < N; ++x) {
		cin >> Arr[x];
	}

	for (y = 0; y < N; ++y) {
		for (x = 0; x < y; ++x) {
			if (Arr[x] < Arr[y]) {
				if (DP[y][0] <= DP[x][0]) {
					DP[y][0] = DP[x][0] + 1;
					DP[y][1] = x;
				}
			}
		}
	}

	int big = 0;
	int big_x = 0;
	for (x = 0; x < N; ++x) {
		if (big < DP[x][0]) {
			big = DP[x][0];
			big_x = x;
		}
	}
	cout << DP[big_x][0] << "\n";

	for (big; big > 0; --big) {
		seq.push(Arr[big_x]);
		big_x = DP[big_x][1];
	}
	while (!seq.empty()) {
		cout << seq.top() << " ";
		seq.pop();
	}
}