알고스팟 _ 합친 LIS

https://www.algospot.com/judge/problem/read/JLIS

algospot.com :: JLIS

 접근

 첫번째 아이디어 

 수열을 합치는게 어떨까 생각했다. 하지만 더 곰곰히 생각해보니 어떻게 합칠지와 시간면에서 통과하는 방법은 아닐것으로 생각되어 패스했다.

 

 두번째 아이디어

 일반적인 LIS를 구하는 방식에서 두 수열을 모두 살펴본다. (종만북의 풀이)

---

 풀이방법

 그냥 LIS와 다를것 없는 풀이방식이다.

 다만 모든 원소들은 32비트 부호 있는 정수에 저장할 수 있습니다. 라는 조건을 고려하여 자료형을 long long을 쓰는것과 두가지 수열을 모두 보는것 정도만 다르다. 그외에 getMaxLength(0, 0)부터 시작해 모든 경우를 해보는것과 마지막 값에서 -2를 해주는것은 ret에서 2를 추가로 더했으니 답에서 -2해주는거라 당연한것이다.(말이 좀이상한데 코드를 잘보면 당연하다 0, 0까지 추가로 + 2를 저장했으니까)  

 종만북은 어떻게 풀었는지 한번 보고풀다보니 종만북 풀이와 거의 유사하다.ㅎ

---

 전체코드

#include <bits/stdc++.h>

using namespace std;
long long A[101];
long long B[101];
int dp[101][101];
int n, m;

void dpInit()
{
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++)
			dp[i][j] = -1;
}

void Input()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> A[i];
	for (int i = 1; i <= m; i++)
		cin >> B[i];
}

long long maxLong = numeric_limits<long long>::min();
int getMaxLength(int aIdx, int bIdx)
{
	int& ret = dp[aIdx][bIdx];
	if (ret != -1) return ret;
	long long a = (aIdx > 0) ? A[aIdx] : maxLong;
	long long b = (bIdx > 0) ? B[bIdx] : maxLong;
	long long maxEle = max(a, b);
	ret = 2;

	for (int nextA = aIdx + 1; nextA <= n; nextA++)
		if (maxEle < A[nextA])
			ret = max(ret, getMaxLength(nextA, bIdx) + 1);

	for (int nextB = bIdx + 1; nextB <= m; nextB++)
		if (maxEle < B[nextB])
			ret = max(ret, getMaxLength(aIdx, nextB) + 1);

	return ret;
}

int main()
{
	int testcase;
	cin >> testcase;
	for (int i = 0; i < testcase; i++)
	{
		Input();
		dpInit();
		cout << getMaxLength(0, 0) - 2 << '\n';
	}
	return 0;
}

---

 후기

 하 문제라기엔 어려운 문제인듯?