백준 14002 c++ "가장 긴 증가하는 부분 수열 4" -PlusUltraCode-

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

 

[필자 사고]

기본적인 LIS 문제에 + 증가하는 숫자에 대한 기록까지 더해져 있는 문제이다.

필자는 LIS문제는 익숙하게 풀었지만

증가하는 숫자들의 기록에서 애를 먹었다.

곰곰히 생각해보니 백트래킹 사고를 기반으로 문제를 풀면 풀 수 있었다.

 

총 LIS길이를 구하고 뒤에서 부터 dp값을 검사하여 같은 길이가 있다 하면 해당 값을 넣는 형식으로 말이다.

발견한다면 현재 길이를 -1 로 해서 갱신해주고 위와 같은 과정을 반복해주면 증가하는 숫자들의 기록을 구할 수 있다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

1. 입력 처리 (Input 함수)
   Input() 함수는 수열의 길이 N을 입력받고, 이를 저장할 벡터 arr와 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)의 길이를 저장할 dp 벡터를 초기화한다.

• dp 벡터는 모든 원소를 1로 초기화하며, 이는 각 원소가 최소한 자기 자신만으로 LIS를 구성할 수 있음을 의미한다.
• arr 벡터에는 입력받은 수열을 저장한다.

1. 최장 증가 부분 수열 계산 (Game_Start 함수)
   Game_Start() 함수는 동적 계획법(DP)을 이용하여 최장 증가 부분 수열을 구하고, 그 구성 요소를 찾아 출력한다.

• dp[i]는 i번째 원소를 끝으로 하는 최장 증가 부분 수열의 길이를 의미한다.
• 이중 루프를 사용하여 dp[i] 값을 갱신한다.
  • arr[i] > arr[k] 조건을 만족하면 dp[i] = max(dp[i], dp[k] + 1)을 수행하여 LIS 값을 갱신한다.
• 이후, max_element(dp.begin() + 1, dp.end())를 이용하여 최장 증가 부분 수열의 길이와 해당 마지막 원소의 인덱스를 찾는다.
• 다시 역순으로 탐색하여 LIS를 구성하는 원소를 mySet에 저장한다.
  • dp[index] == len 조건을 만족하는 원소를 mySet에 추가하면서 len을 감소시켜 LIS의 원래 순서를 유지한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;

int N;
vector<int> dp;
vector<int> arr;
set<int> mySet;

void Input() {
	cin >> N;
	dp.resize(N + 1,1);
	arr.resize(N + 1);
	
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
}

void Game_Start() {
	int resultIdx = -1;
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k < i; k++) {
			if (arr[i] > arr[k]) {
				dp[i] = max(dp[i], dp[k] + 1);
			
			}
		}
	}

	resultIdx = max_element(dp.begin() + 1, dp.end()) - dp.begin();
	int len = *max_element(dp.begin() + 1, dp.end());
	for (int index = resultIdx; index >= 1; index--) {
		if (dp[index] == len) {
			mySet.insert(arr[index]);
			len--;
		}
	}

	cout << *max_element(dp.begin() + 1, dp.end()) << '\n';
	for (int num : mySet) {
		cout << num << " ";
	}
}

int main(void) {
	Input();
	Game_Start();
}