<종만북> 08. 동적계획법_합친 LIS (JLIS, Joined Longest Increasing Subsequence

앞에서 LIS 문제는 많이 다뤘다. 하지만 이번에 다룰 내용은 더 심화된 JLIS 문제이다. 근데 책에서는 난이도가 하 라고 되어있다..하하..

예를 들어 '1 3 4 7 9'은 '1 9 4'와 '3 4 7'의 JLIS이다. 문제는 정수 수열 A, B가 주어질 때 JLIS의 길이를 계산하는 프로그램이다.

먼저 책에서 LIS 문제를 해결하는 동적 계획법 알고리즘을 알아볼 필요가 있다.

코드8.11

int n;
int cache[100], S[100];
int list(int start) {
	int& ret = cache[start];

	if (ret != -1) return ret;

	ret = 1; 
	for (int next = start + 1; next < n; ++next)
		if (S[start] < S[next])
			ret = max(ret, list(next) + 1);

	return ret;
}

1. list()는 S(start)에서 시작하는 증가 부분 수열 중 최대 길이를 반환하는 함수이다.

2. ret가 cache[a][b]에 대한 참조형(reference)이다. ret 의 값을 바꾸면 cache[a][b]의 값도 변하기 때문에 매번 귀찮게 cache[a][b]라고 쓰지 않고, 실수를 줄여주기 위해 사용한다.

3. ret=1 로 설정하는 이유는 항상 S[start]는 있기 때문에 길이를 최하 1로 설정한다.

이 코드에서는 list()를 호출할 때 항상 증가 부분 수열의 시작 위치를 지정해 줘야 하므로 처음에 호출할 때 각 위치를 순회하며 최댓값을 찾는 코드를 작성해줘야 한다.

int maxLen = 0;
for (int begin = 0; begin < n; ++begin) 
	maxLen = max(maxLen, list(begin));

그래서 책에서는 S[-1]을 아주 작은 수, 즉 마이너스 무한대로 설정해놓고 list(-1)를 호출하면 모든 시작 위치를 자동으로 시도하게 되는 코드를 만들었다.

코드8.12

int n;
int cache[101], S[100];

int list(int start) {
	int& ret = cache[start + 1];
	if (ret != -1) return ret;

	ret = 1;
	for (int next = start + 1; next < n; ++next)
		if (start == -1 || S[start] < S[next])
			ret = max(ret, list(next) + 1);
	return ret;
}

1. start=-1로 주어질 수도 있기 때문에 cache[]에 접근할 때 cache[start] 대신 cache[start+1]을 쓴다. 따라서 cache[]의 크기도 1 커졌다.
2. 결과 값은 list(-1)-1 을 해야하다. S[-1]은 가상으로 추가한 입력 값이기 때문에 최종 반환 값에서는 1을 빼준다.

그럼 이제 jlis를 푸는 알고리즘을 생각해보자.

1. jlis(index A, index B)=A[indexA], B[indexB]에서 시작하는 합친 증가 부분 수열의 최대 길이이다.
2. A[indexA]와 B[indexB]중 작은 값이 앞에 온다.
3. 이 증가 부분 수열의 다음 숫자는 A[index+1] 이후 혹은 B[index+1] 이후의 수열 중 max(A[indexA], B[indexB])보다 큰 수 중 하나가 된다.
4. A[nextA]를 다음 숫자로 선택했을 경우에 합친 증가 부분 수열의 최대 길이는 1+jlis(nextA, indexB)가 된다.

와 같은 점화식으로 나타낼 수 있다.

const long long NEGINF = numeric_limits<long long>::min();
int n, m, A[100], B[100];
int cache[101][101];

int jlis(int indexA, int indexB) {
	int& ret = cache[indexA + 1][indexB + 1];
	if (ret != -1) return ret;

	ret = 2;
	long long a = (indexA == -1 ? NEGINF : A[indexA]);
	long long b = (indexB == -1 ? NEGINF : B[indexB]);
	long long maxElement = max(a, b);

	for (int nextA = indexA + 1; nextA < n; ++nextA)
		if (maxElement < A[nextA])
			ret = max(ret, jlis(nextA, indexB) + 1);
	for (int nextB = indexB + 1; nextB < n; ++nextB)
		if (maxElement < B[nextB])
			ret = max(ret, jlis(indexA, nextB) + 1);
	return ret;
}

int main() {

	cin >> n >> m;
	memset(cache, -1, sizeof(cache));
	for (int i = 0; i < n; i++)
		cin >> A[i];
	for (int j= 0; j < m; j++)
		cin >> B[j];

	cout << jlis(-1, -1) - 2 << endl;

	return 0;
}

1. std::numeric_limits 클래스는 자료형의 max, min값을 알아내기 위해 선언한 것인데, indexA, indexB==-1 일 경우 마이너스 무한대 값으로 설정하기 위해서다.
2. A[indexA], B[indexB] 가 이미 존재하므로 ret=2로 항상 초기화 한다.
3. A[-1], B[-1]은 가상으로 추가한 입력 값이기 때문에 최종 반환값에서 -2를 해줘야 한다.
4. 참고로 memset()으로 int 배열을 초기화 할 때는 -1, 0으로만 '운좋게' 가능하다. 1byte 단위로 값을 초기화 하기 때문에 char type 에서 초기화 할 때 사용된다.