백준 14003번 가장 긴 증가하는 부분 수열 5

문제

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

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

  

문제풀이

사용한 알고리즘 : LIS

(0) 생각

 가장 긴 증가하는 부분 수열 (LIS) 를 구하는 문제입니다. 제가알기론 LIS 는 크게 DP를 이용한 풀이법과 segtree를 이용한 풀이법이 있습니다. (물론 더 좋은 풀이가 있을 수 있습니다.)
 저는 DP를 사용하여 문제를 해결하였습니다. ( 사실 lower_bound 만 쓴 것 같습니다. )
 제가 쓴 풀이가 이해하기 어려운 것 같습니다. 부족한 설명 죄송합니다... 쉽게 풀어 설명하기가 쉽지가 않네요... segtree를 이용한 풀이가 이해하기에는 더 쉬우니 다음에 올려놓겠습니다. (아마...)

 제가 작성한 최장 증가 수열의 비슷한 문제 링크를 올립니다.

 segtree를 통한 풀이도 작성하여 놓았습니다!

 백준 3745번 오름세

(1) 코드 9~12

 입력받은 수열을 i=0~>N-1 순으로 탐색 하면서 만들 수 있는 x길이의 LIS를 구성하는 성분들을 dp로 설정하였습니다.
 탐색을 하면서 arr[i] 를 포함하는 LIS 길이를 따로 배열을 만들어 저장해주었습니다. (탐색이 끝난 후 LIS 구성을 찾기위해)

(2) 코드 16~33

 i=0~>N-1 순으로 탐색하며 LIS를 구해주었습니다.
 i번째 탐색시 이전 1~i-1까지로 만든 LIS 의 배열의 끝값(dp로저장) 보다 arr[i]가 큰 경우, arr[i]를 끝값으로 붙여주었고, 그렇지 않은경우 해당 arr[i]가 들어갈 자리를 lower_bound로 탐색하여 찾아주었습니다.
 각 탐색마다 arr[i]를 끝값으로하는 LIS 길이를 따로 저장해주었습니다.

(3) 코드 41~48

 저장해 놓은 각 arr[i]를 끝값으로 하는 LIS 길이를 뒤에서부터 탐색하며 최종 LIS 구성을 찾아주었습니다.

	#include <iostream>
	#include <stack>
	#include <algorithm>
	using namespace std;
	const int MAX = 1e6;
	int N;
	int arr[MAX+1];
	// dp[x] : 만들 수 있는 x길이의 LIS의 구성 성분
	int dp[MAX+1];
	// howmany[x] : arr[x]를 포함해 만들 수 있는 LIS 길이
	int howmany[MAX+1];
	// 정답
	stack<int> St;
	int LIS(void){
	int idx = 0;
	dp[idx] = arr[0];
	howmany[0] = 1;
	for(int i=1; i<N; ++i){
	if(dp[idx] < arr[i]){
	dp[++idx] = arr[i];
	howmany[i] = idx+1;
	}
	else{
	int idx2 = lower_bound(dp,dp+idx,arr[i]) - dp;
	dp[idx2] = arr[i];
	howmany[i] = idx2+1;
	}
	}
	return idx+1;
	}
	int main(){ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for(int i=0; i<N; ++i) cin >> arr[i];
	int result = LIS();
	cout << result << '\n';
	// 뒤에서 부터 탐색
	for(int i=N-1; i>=0; i--){
	// arr[i]를 포함한 LIS 길이 = result 인 경우 arr[i]를 답으로!
	if(howmany[i]==result){
	St.push(arr[i]);
	result--;
	}
	}
	// 정답 출력
	while(!St.empty()){
	cout << St.top() << ' ';
	St.pop();
	}
	return 0;
	}

view raw BOJ 14003.cpp hosted with ❤ by GitHub