8.5_합친 LIS_JLIS

문제 설명

 

algospot.com :: JLIS

• 부분 수열 : 어떤 수열에서 0개 이상의 숫자를 지운 결과
• 증가 부분 수열 : 부분 수열 중 오름차순으로 정렬된 수열
• 최장 증가 부분 수열(LIS) : 증가 부분 수열 중 길이가 가장 긴 수열
• 합친 증가 부분 수열 : 두 개의 정수 수열 A와 B에서 각각 증가 부분 수열을 얻은 뒤 합친 것
• 합친 최장 증가 부분 수열(JLIS) : 합친 증가 부분 수열 중 길이가 가장 긴 수열

=> 정수 수열 A와 B가 주어질 때 JLIS의 길이를 출력하기

 

 

문제 풀이

LIS를 만드는 방법은 단순하다.

한 숫자를 고르면 그 뒤에는 더 큰 숫자를 고르면 된다.

 

그러므로 A수열의 인덱스, B수열의 인덱스를 파라미터로 받는 재귀함수를 이용해 JLIS를 구할 수 있다.

 

문제에서 주어지는 모든 원소들은 32비트 부호 있는 정수에 저장할 수 있다고 한다.

그렇다면 처음 시작할때는 32비트 음수 정수보다 작은 수로 시작해야 그 다음 정수를 고를 수 있다.

 

따라서 long long 형의 최솟값을 시작값으로 하여 그 다음 원소를 골라준다.

 

문제 풀이 코드

#include <iostream>
#include <string.h>
#include <limits>

using namespace std;

int nSize, mSize;
int n[100], m[100];
int memoization[101][101];
const long long NEGINF = numeric_limits<long long>::min();

long long getMaxLong(long long a, long long b) {
	if (a > b) return a;
	return b;
}

int getMaxInt(int a, int b) {
	if (a > b) return a;
	return b;
}

// [nIndex~n의 끝] & [mIndex~m의 끝] 배열 중 가장 긴 JLIS를 구하는 최대 부분 수열 길이 구하기
int makeJLIS(int nIndex, int mIndex) {
	int result = memoization[nIndex + 1][mIndex + 1];
	if (result != -1) {
		return result;
	}
	// n[nIndex], m[mIndex]는 존재하므로 2개는 항상 있다.
	// 맨 앞 원소는 항상 포함한다고 가정(n[-1] = m[-1] = -무한대)(= 제일 작은 수)
  	// "-무한대"에 대한 개수
	result = 2;

	long long a = (nIndex == -1 ? NEGINF : n[nIndex]);
	long long b = (mIndex == -1 ? NEGINF : m[mIndex]);
	long long maxElement = getMaxLong(a, b);

	for (int nextN = nIndex + 1; nextN < nSize; ++nextN) {
		if (maxElement < n[nextN])
			result = getMaxInt(result, makeJLIS(nextN, mIndex) + 1);
	}
	for (int nextM = mIndex + 1; nextM < mSize; ++nextM) {
		if (maxElement < m[nextM])
			result = getMaxInt(result, makeJLIS(nIndex, nextM) + 1);
	}
	memoization[nIndex + 1][mIndex + 1] = result;
	return result;
}


int main() {
	int C;
	cin >> C;
	for (int tc = 1; tc <= C; ++tc) {
		cin >> nSize >> mSize;
		for (int i = 0; i < nSize; ++i) {
			cin >> n[i];
		}
		for (int j = 0; j < mSize; ++j) {
			cin >> m[j];
		}

		memset(memoization, -1, 101 * 101 * sizeof(int));
		// 맨 앞 원소(n[-1], m[-1])도 항상 포함한다고 가정했으니, 마지막에 제외해주기
		cout << makeJLIS(-1, -1) - 2 << endl;
	}
	return 0;
}