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

가장 긴 증가하는 부분 수열 4 (백준 Gold 4)

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

수열 A가 주어졌을 때
가장 긴 증가하는 부분 수열(LIS)과 그 길이를 구하는 문제

• 길이가 같다면 그 중 아무거나 출력한다
  

풀이 방법

LIS는 자주 볼 수 있는 DP계열 문제로서
다음과 같은 점화식을 주로 가진다

dp[i] : A(i)까지 진행하였을때의 가장 긴 LIS의 길이
dp[i] = dp[j] + 1(v[i] > v[j]), dp[j] (v[i] <= v[j])

다만 이 문제는
행렬 또한 출력해야 하기에
일부 부분을 수정하여 문제를 풀었다

1. Pair<int,int>를 통해
   first : LIS 길이
   second : 왼쪽에서 나보다 작은, 그리고 큰 값을 가진 LIS 위치
   

2. first 부분을 통해 위쪽의 dp 축적을 하는 동시에
   값이 갱신되었다면 second 값을 갱신
   (second는 초기에는 ‘자기 자신’)
   

3. dp 진행 후
   while문을 통하여 stack에 넣어주며
   행렬을 역추적
   

다만 처음 풀때, 무조건 n-1 의 위치에서 시작하니
정확도 오류가 발생하였기에
반복문을 한번정도 돌면서 시작 위치를 정해주었다
(+ 역추적의 시작 위치)

제출 코드

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

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

	int n;
	cin >> n;

	vector<int> vecs(n);

	for (int i = 0; i < n; i++)
		cin >> vecs[i];

	if (n == 1)
	{
		cout << 1 << '\n';
		cout << vecs[0];
		return 0;
	}

	vector<pair<int, int>> dp(n);
	dp[0] = { 1, 0 };

	for (int i = 1; i < n; i++)
	{
		dp[i] = { 1,i };

		for (int j = i - 1; j >= 0; j--)
		{
			if (vecs[i] > vecs[j] &&
				dp[i].first <= dp[j].first)
			{
				dp[i].first = dp[j].first + 1;
				dp[i].second = j;
			}
		}
	}

	int ans = 0;
	int sIdx = 0;

	for (int i = 0; i < n; i++)
	{
		if (ans < dp[i].first)
		{
			ans = dp[i].first;
			sIdx = i;
		}
	}

	cout << ans << '\n';
	stack<int> st;

	int next = sIdx;

	while (next != dp[next].second)
	{
		st.push(next);
		next = dp[next].second;
	}

	st.push(next);

	while (st.empty() == false)
	{
		cout << vecs[st.top()] << ' ';
		st.pop();
	}

	return 0;
}

결과

사실 예전에 풀어보려 하다 못 푼 문제이다
(풀려는 프로젝트에 이미 파일이 있었다…)

LIS 자체를 풀 생각은 해본적이 있으나
‘행렬’을 어떻게 출력하지에 대한 고민을 하다 결국 못 푼 문제였기에
마무리를 지어주었다!