알고리즘 문제해결 전략 Chapter 08 - JLIS(C++)

포타토·2020년 1월 5일

알고리즘

목록 보기

18/76

예제: 합친 LIS

문제
어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부르지요. 예를 들어 '3 6 9'는 앞의 수열의 증가 부분 수열입니다.

두 개의 정수 수열 A 와 B 에서 각각 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로 합친 것을 합친 증가 부분 수열이라고 부르기로 합시다. 이 중 가장 긴 수열을 합친 LIS(JLIS, Joined Longest Increasing Subsequence)이라고 부릅시다. 예를 들어 '1 3 4 7 9' 은 '1 9 4' 와 '3 4 7' 의 JLIS입니다. '1 9' 와 '3 4 7' 을 합쳐 '1 3 4 7 9'를 얻을 수 있기 때문이지요.

A 와 B 가 주어질 때, JLIS의 길이를 계산하는 프로그램을 작성하세요.

입력
입력의 첫 줄에는 테스트 케이스의 수 c ( 1 <= c <= 50 ) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 A 와 B 의 길이 n 과 m 이 주어집니다 (1 <= n,m <= 100). 다음 줄에는 n 개의 정수로 A 의 원소들이, 그 다음 줄에는 m 개의 정수로 B 의 원소들이 주어집니다. 모든 원소들은 32비트 부호 있는 정수에 저장할 수 있습니다.

출력
각 테스트 케이스마다 한 줄에, JLIS 의 길이를 출력합니다.

예제 입력
3
3 3
1 2 4
3 4 7
3 3
1 2 3
4 5 6
5 3
10 20 30 1 2
10 20 30
예제 출력
5
6
5

풀이

이전에 포스팅했던 LIS 문제의 심화 버전이다.

나중에 후기에 적겠지만, 너무너무 고생한 문제이다. 막상 풀어놓고 보니 별 거 없었지만, 도서 풀이와 다르게 하려다보니 뭔가에 사로잡혀 엄청나게 오래 걸렸다.

또한, 문제에 함정이 있다. 입력부에서 모든 원소들은 32비트 부호 있는 정수에 저장할 수 있다고 되어있다. 그 말인 즉슨, int형 자료형의 모든 입력이 들어온다는 소리이다. 따라서, MIN 값을 설정하고 싶다면 32비트보다 더 큰 자료형을 써야한다. 그러나 필자는 좀 다른 방법을 사용하였기 때문에, 위의 방법을 쓸 필요는 없다.

LIS와의 차이점은, LIS는 다음번 index 번호만 넘겨 해당 index의 값과 다음 값을 비교했지만, JLIS는 두 개의 수열이 있기 때문에 어느 값이 기준이 되었는지 알 수 없다. 따라서, 매개변수를 하나 더 만들어서 현재 선택된 값을 넘겨준 후 그 값과 비교를 한다.

그리고 처음 A index와 B index의 값을 -1로 넘겨주는 이유는, 2중 for문과 같은 개념으로 두 개의 수열의 모든 위치에서 값을 비교하기 위해서이다.

처음에 필자는 main문에서

for(int i = 0; i < n; i++){
	for(int j = 0; j < m; j++){
    	res = max(res, jlis(i, j, min(A[i], B[j]));
	}
}

이런 요상한 방식으로 접근을 했었는데, 그러면 cache에 (0, 0) 위치에서 시작했을때의 값이 저장되어 버리기 때문에 제대로 된 값이 나오지 않는다.

전체적인 소스코드는 아래와 같다.

소스 코드

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int n, m;
int A[100], B[100];
int cache[101][101];

int jlis(int aidx, int bidx, int num) {
	int& res = cache[aidx + 1][bidx + 1];
	if (res != -1) return res;

	res = 2;
	for (int i = aidx + 1; i < n; i++) {
		if ((aidx == -1 && bidx == -1) || num < A[i]) {
			res = max(res, jlis(i, bidx, A[i]) + 1);
		}
	}
	for (int i = bidx + 1; i < m; i++) {
		if ((aidx == -1 && bidx == -1) || num < B[i]) {
			res = max(res, jlis(aidx, i, B[i]) + 1);
		}
	}

	return res;
}

int main() {

	int testCase;
	cin >> testCase;

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

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

	return 0;
}