문제

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

풀이

이 문제를 완전 처음에.. 그러니까 동적계획법이 뭔지도 모르고 접했을때는 그냥 두 수열을 중복되는 수 없이 한 수열로 합친 다음에 합친 수열의 길이를 출력하게 했다. 놀랍게도 이 방식이 예제 입력에 대해서는 제대로 된 답을 출력해주기 때문에 코드를 제출했으나 당연히 WA를 받았다.

그리고 몇 일 전에 LIS 문제를 해결한 뒤 이 문제를 다시 접했는데 이 때는 LIS와 비슷하게 해결하면 될 줄 알았다. 두 수열의 LIS를 각각 구한뒤 각 수열의 길이를 출력하는 방법을 생각해보았으나 세 번째 예제인 $A=\{10, 20, 30\}, B=\{10, 20, 30, 1, 2\}$같은 경우에서는 A,B 수열 모두 $\{10, 20, 30\}$가 LIS이므로 6을 반환하지만 실제로는 $A=\{10, 20, 30\}, B=\{1, 2\}$인 5가 답이다.

LIS 문제는 한 개의 수열에 대한 인덱스 값을 인수로 받는 solve(int)를 작성했었는데 이 문제도 비슷하게 두개의 수열의 인덱스 값을 각각 받는 solve(int, int)를 작성하면 될 것 같았다. 문제를 해결하는 코드를 작성하면서 아래와 같은 부분에 대해 유의하며 작성했다.

• 모든 원소의 값은 signed integer 범위에 들어간다. 즉, 최소값은 INT_MIN이다.
• 한 수열의 원소를 아무것도 선택하지 않는 상태가 있을 수 있다.

#include <cstdio>
#include <cstring>
#include <climits>
int n,m,A[100],B[100],dp[101][101];
int max(int a, int b){return a>b?a:b;}
int solve(int Ai, int Bi){
	int &ret = dp[Ai+1][Bi+1];
	if(ret != -1) return ret;
	ret = 0;
	int pA, pB, pivot;
	pA = Ai == -1 ? INT_MIN : A[Ai];
	pB = Bi == -1 ? INT_MIN : B[Bi];
	pivot = max(pA,pB);
	for(int i=Ai+1;i<n;i++)
		if(pivot < A[i])
			ret = max(ret, solve(i,Bi)+1);
	for(int i=Bi+1;i<m;i++)
		if(pivot < B[i])
			ret = max(ret, solve(Ai,i)+1);
	return ret;
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--){
		int i;
		memset(A,0,sizeof(A));
		memset(B,0,sizeof(B));
		memset(dp,-1,sizeof(int)*101*101);
		scanf("%d%d",&n,&m);
		for(i=0;i<n;i++)
			scanf("%d",&A[i]);
		for(i=0;i<m;i++)
			scanf("%d",&B[i]); 
		printf("%d\n",solve(-1,-1));
	}
}

문제

#include <stdio.h>
int n,num[500];
int max(int a,int b){return a>b?a:b;}
int solve(int pos){
	int i, ret = 0;
	for(i=pos+1;i<n;i++){
		if(num[pos] < num[i]){
			ret = max(ret, solve(i)+1);
		}
	}
	return ret;
}
int main(void) {
	int i,t;
	scanf("%d",&t);
	while(t--){
		int ans = 0;
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d",&num[i]);
		}
		for(i=0;i<n-1;i++){
			ans = max(ans, solve(i));
		}
		printf("%d\n",ans);
	}
	return 0;
}

위 코드는 메모이제이션을 적용하지 않은 코드라 같은 값을 여러번 구한다. 그러니 여기서 메모이제이션을 적용해줘야한다. 메모이제이션을 적용할 dp 배열을 만들고 dp[x] = x번째 수부터 시작할때 가장 긴 LIS의 길이의 값을 저장하게 하였다.

#include <stdio.h>
#include <string.h>
int n,num[500],dp[500]; //dp[x] == -1이면 x번째 수부터 시작하는 LIS 길이를 아직 구하지 않은것이다
int max(int a,int b){return a>b?a:b;}
int solve(int pos){
	int i, ret = 1;
	//이미 pos번째 수부터 시작하는 LIS 길이를 구했다면 바로 반환한다.
	if(dp[pos] != -1) return dp[pos];
	
	//pos번째 수보다 뒤에있는 더 큰 모든 수들을 확인하며 LIS의 길이를 찾는다.
	for(i=pos+1;i<n;i++)
		if(num[pos] < num[i])
			ret = max(ret, solve(i)+1);
	//메모이제이션하고 반환한다.
	return dp[pos] = ret;
}
int main(void) {
	int i,t;
	scanf("%d",&t);
	while(t--){
		int ans = 0;
		memset(dp,-1,sizeof(dp));
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%d",&num[i]);
		//0번째 수부터 n-1번째 수까지 돌면서 LIS 길이를 찾는다.
		for(i=0;i<n-1;i++)
			ans = max(ans, solve(i));
		
		printf("%d\n",ans);
	}
	return 0;
}