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

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

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

 

1. 풀이방법

 

이 문제는 dp를 활용해서 가장 긴 증가하는 부분 수열의 개수와 수열을 출력하는 문제이다.

그러므로 원래 LIS보다 저번에 방문했던 인덱스를 저장할 배열이 하나 더 필요하다.

 

하지만, 나는 그냥 dp를 pair로 만들어서 ( 지금까지의 수열의 개수, 전에 방문한 인덱스 ) 이렇게 만들었다.

근데 그냥 배열하나 더 만드는게 속편하다.

 

ex) 내가 푼 방법

인덱스	1	2	3	4	5	6
수열	10	20	10	30	20	6
dp( 개수 )	1	2	1	3	2	4
dp( 전 인덱스)	0	1	0	2	3	4

 

---

 

2. 코드

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int arr[1002];
//length, idx
vector<pair<int, int>>dp;

int main()
{
	vector<int> answer;
	int n;
	cin >> n;
	int maxLong = 0;
	dp.resize(n + 2);
	
	int value;
	for (int i = 1; i <= n; i++)
	{
		cin >> value;
		arr[i] = value;

		//입력 받으면서 dp 입력
		for (int j = i-1; j >= 0; j--)
		{
			if (arr[i] > arr[j] && dp[i].first < dp[j].first + 1)
			{
				dp[i] = { dp[j].first + 1, j };
				maxLong = max(dp[i].first, maxLong);
			}
		}
	}

	//answer에 최장수열의 요소 저장
	for (int i = n; i > 0; i--)
	{
		if (dp[i].first == maxLong)
		{
			while (1)
			{
				answer.push_back(arr[i]);
				int next = dp[i].second;
				i = next;

				if (i == 0)
					break;
			}

			break;
		}
	}

	cout << maxLong << '\n';
    
    	//뒤부터 넣었으니 reverse 해주어야함 
	reverse(begin(answer), end(answer));
	for (auto& ele : answer)
	{
		if (ele == 0)
			continue;
		cout << ele << ' ';
	}

	return 0;
}

 

---

 

3. 후기

 

아까 사이클 제거 문제 풀다가 멘탈터졌는데 이거 풀면서 약간 회복됬다.