[Algospot] 합친 LIS (문제 ID : JLIS)

문제

어떤 수열에서 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 의 길이를 출력합니다.

---

두 배열 A와 B를 합쳐서 가장 긴 증가하는 부분 수열을 만드는 문제이다. 책을 보고도 이해가 좀 힘들었던 문제다. 게다가 문제 조건에 모든 부호있는 정수가 들어올 수 있다고 해서 int 최소값을 사용하는게 더 귀찮게 만든 것 같다. index를 왜 -1부터 넣어야 하는지도 이해를 못 했다. 아무튼 문제를 푸는 방법은 A와 B의 인덱스 a, b에서 dp[a][b] = max(dp[na][b]+1, dp[a][nb] + 1)이다. 다만 na가 a+1일수도 있고 a+2 ... 등 모든 값이 들어올 수 있기 때문에 a+1부터 N까지 모든 값을 넣어서 완전탐색을 하면 된다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/JLIS.cpp

chosh95/STUDY

C++ 코드 

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
const long long NEGINF = numeric_limits<long long>::min();
int C, N, M;
int A[102], B[102];
int dp[102][102];

int jlis(int a, int b) //AÀÇ index, BÀÇ index
{
	int& ret = dp[a + 1][b + 1];
	if (ret != -1) return ret;
	ret = 0;
	long long aa = (a == -1 ? NEGINF : A[a]);
	long long bb = (b == -1 ? NEGINF : B[b]);
	long long maxElement = max(aa, bb);

	for (int na = a + 1; na < N; na++) {
		if (maxElement < A[na]) {
			ret = max(ret, jlis(na, b) + 1);
		}
	}
	for (int nb = b + 1; nb < M; nb++) {
		if (maxElement < B[nb]) {
			ret = max(ret, jlis(a, nb) + 1);
		}
	}
	return ret;
}

int main()
{
	cin >> C;
	while (C--) {
		memset(dp, -1, sizeof(dp));
		cin >> N >> M;
		for (int i = 0; i < N; i++) cin >> A[i];
		for (int j = 0; j < M; j++) cin >> B[j];
		cout << jlis(-1, -1) << endl;
	}
}