[LIS(Longest Increasing Subsequence)] 응용 문제: 징검다리2_소프티어

응용 문제: 징검다리2_소프티어

source: https://softeer.ai/practice/info.do?idx=1&eid=393

---

풀이1. 탑다운 다이내믹 프로그래밍 방식 풀이

아래 풀이는 사실상 O(N^3)에 메모제이션 기법을 추가한 것이다. 따라서 소프티어 플랫폼에선 시간 초과가 발생하였다.

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

int N;
vector<int> Dari(300000);

int DP[300000][2];

int DFS(int idx, bool ASC) {
	// DP 활용
	if (DP[idx][ASC] != 0)
		return DP[idx][ASC];

	int maxCnt = 1;

	if (ASC) {
		for (int i = idx + 1; i < N; i++) {
			if (Dari[idx] < Dari[i])
				maxCnt = max(maxCnt, 1 + DFS(i, ASC));
			else {
				maxCnt = max(maxCnt, 1 + DFS(i, !ASC));
			}
		}
	}
	else {
		for (int i = idx + 1; i < N; i++) {
			if (Dari[idx] <= Dari[i])
				continue;

			maxCnt = max(maxCnt, 1 + DFS(i, ASC));
		}
	}

	DP[idx][ASC] = maxCnt;
	return maxCnt;
}

int solution() {
	int MAX_CNT = 0;
	for (int i = 0; i < N; i++) {			// O(N)
		MAX_CNT = max(MAX_CNT, DFS(i, true));	// O(N^2)
	}
    // => total: O(N^3) with 메모제이션

	return MAX_CNT;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Dari[i];
	}

	int answer = solution();
	cout << answer << endl;

	return 0;
}

---

풀이2. 개선된 LIS 알고리즘을 활용한 풀이

앞선 포스팅의 O(NlogN)으로 LIS 문제를 해결하는 알고리즘을 응용하여 푼 풀이이다.

referce: https://www.youtube.com/watch?v=HbbZiUT194s&t=1s

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

int N;
vector<int> Sequence(300000);

void MakeLIS(const vector<int>& Sequence, vector<int>& LIS) {
	vector<int> DP;

	for (int i = 0; i < N; i++) {
		int nowIdx = i;
		int nowNum = Sequence[i];

		if (DP.size() == 0) {
			DP.push_back(nowNum);
			LIS[nowIdx] = 1;
			continue;
		}

		if (DP[DP.size() - 1] < nowNum) {
			DP.push_back(nowNum);
			LIS[nowIdx] = DP.size();
			continue;
		}

		// 이진탐색
		int start = 0;
		int end = DP.size() - 1;
		int lastIdx = -1;
		while (start <= end) {
			int mid = (start + end) / 2;

			if (DP[mid] == nowNum) {
				lastIdx = mid;
				break;
			}
			else if (DP[mid] > nowNum) {
				lastIdx = mid;
				end = mid - 1;
			}
			else {
				start = mid + 1;
			}
		}
		
		if (lastIdx != -1) {
			LIS[nowIdx] = lastIdx + 1;
			DP[lastIdx] = nowNum;
		}
	}
}

int solution() {
	// (1) 각 인덱스까지의 최장 증가 부분수열 길이 구하기 (LIS 배열)
	vector<int> LIS(N);
	MakeLIS(Sequence, LIS);

	// (2) (역순으로) 각 인덱스까지의 최장 증가 부분수열 길이 구하기 (RLIS 배열)
	vector<int> RLIS(N);
	vector<int> ReverseSeq(N);
	for (int i = 0; i < N; i++) {
		ReverseSeq[N - 1 - i] = Sequence[i];
	}
	MakeLIS(ReverseSeq, RLIS);
	
	for (int i = 0; i < N/2; i++) {
		int temp = RLIS[i];
		RLIS[i] = RLIS[N - 1 - i];
		RLIS[N - 1 - i] = temp;
	}

	// (3) i: 0 ~ N-1
	// LIS[i] + RLIS[i] - 1 최대 값 구하기
	int maxCnt = 0;
	for (int i = 0; i < N; i++) {
		maxCnt = max(maxCnt, LIS[i] + RLIS[i] - 1);
	}

	return maxCnt;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Sequence[i];
	}

	int answer = solution();
	cout << answer << endl;
	
	return 0;
}