JLIS

1. 문제 해설

- 기존에 사용했던 LIS 재귀 DP 알고리즘을 변형하여 사용한다.

- JLIS(idxA, idxB) = A[idxA]와 B[idxB]에서 시작하는 합친 증가 부분수열의 최대 길이

2. 이해해야 할 핵심 사항

1) A[idxA]와 B[idxB]를 무조건 포함하는 LIS

: LIS를 구하는데 있어서 두 배열의 임의의 인자값을 포함하거나 포함하지 않을 수 있다. 하지만, LIS를 구할 때처럼 인덱스의 선택/미선택을 재귀함수 내에서 고민하지 않는다. 즉 현재 JLIS 함수 내에 정해진 A배열 인덱스 값과(idxA) B배열의 인덱스 값(idxB)은 무조건 포함하는 LIS를 구하는 방식이다.

2) 시작 인덱스를 A[-1], B[-1]로 접근한다.

: A[-1], B[-1]에 각각 음의 무한대가 들어있다고 가정한다. jlis(idxA, idxB)를 호출했을 경우 아래와 같다.

int a = A[idxA]; int b = B[idxB]; int seq0 = min(a,b);  int seq1 = max(a,b); → 이 때, [seq0, seq1, …] 로 시작하는 JLIS를 반환환다.

만약 main 함수에서 JLIS로 처음 시작하는데 있어서 음수 인자를 사용하지 않으면 

A배열과 B배열의 처음 선택되는 인자 2개 값을 모두 선정해서 call 해줘야 한다. 즉 100*100번의 call이 발생한다.

main()  … int ans = 0; for(int i=0; i<a.len; i++) { for(int j=0; j<b.len; j++ { ans = Math.max(ans, JLIS(i, j)); } } System.out.println(ans); }

이를 main에서 이러한 경우를 없애고, 초기 호출 경우를 재귀함수 내에 녹이는 개념이라고 생각하면 좋을 것 같다.

main() { … int ans = 0; ans = JLIS(-1, -1); System.out.println(ans); }

즉, JLIS(-1, -1)을 호출하면 항상 -∞부터 시작하기 때문에 모든 시작 위치를 자동으로 시도하게 된다.

 * 유의사항

① start = -1인 경우, cache[][]에 접근할 때 cache[start][start] 대신 cache[start+1][start+1]로 쓰는 것을 유의해야한다. 따라서, cache 크기도 1 크게 선언해야한다.

② 결과값에서 -2를 해줘야한다.
    A[-1], B[-1]은 가상으로 추가한 입력 값이기 때문에, 최종 결과값에 -1,-1 두 개의 값이 반영되기 때문이다. 
    따라서, 최종 반환 값에서 빼 줘야한다.

※ 정답 : System.out.println(JLIS(-1, -1) -2);

    

3) A[idxA] != B[idxB] 인 경우는 호출되지 않는다. 

: JLIS 함수 내 선택된 두 인자의 maxElement보다 큰 값을 next idx로 선택하여 재귀호출을 진행하기 때문이다.

※ 참고 : 종만북, https://algospot.com/forum/read/1851/