[알고스팟] JLIS - 합친 LIS (C++)

문제

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

algospot.com :: JLIS

 

풀이

일단 이전 단계 문제인 LIS(최장 증가 부분 수열) 문제를 확인하고 옵시다.

 

LIS보다 까다로워진 문제입니다.

단순히 생각했을 때 두 수열의 LIS의 길이를 더하면 된다고 생각할 수 있지만

 

1 4 9 4 -> lis length: 3

3 4 4 7 -> lis length: 3

위의 예제에서는 JLIS는 1 3 4 7 9인 5이지만 각각의 LIS 길이를 더하면 6으로 오답이 나옵니다. 

 

따라서 LIS에서처럼 각각의 위치에서부터의 최장 길이를 모두 계산해 보아야 합니다.

입력의 크기는 100 이하이기 때문에 O(nm)으로 충분히 해결이 가능합니다.

 

 

재귀함수 int findJLIS(int idx_a, int idx_b)는 해당 위치의 값들을 포함하는 최장 길이를 반환합니다.

dp[idx_a][idx_b]는 해당 위치의 값들을 포함하는 최장 길이를 저장한다.

 

방문한 값이 아니라면 현재 idx_a와 idx_b의 값 중에서 더 큰 값max_value 를 찾습니다.

 

1.idx_b 값은 그대로 두고, idx_a+1 부터 a_length까지 방문합니다.

  해당 값이 max_value보다 크다면 JLIS를 이어갈 수 있으므로 

 해당 위치를 선택한  JLIS길이는 1+ findJLIS(next_idx_a,idx_b)이 됩니다.

 

2. idx_a 값은 그대로 두고, idx_b+1 부터 b_length까지 방문합니다.

  해당 값이 max_value보다 크다면 JLIS를 이어갈 수 있으므로 

 해당 위치를 선택한  JLIS길이는 1+ findJLIS(idx_a,next_idx_b)이 됩니다.

 

1,2를 모두 수행한 값 중 가장 큰 값이 dp[idx_a][idx_b]의 값이 됩니다.

 

추가적으로 코드를 구현하기 위해 

arr_a[0]값과 arr_b[0]값은 32bit의 signed int 보다 작은 값으로 설정한 후

findJLIS(0,0)을 호출해주면  arr_a[1]값과 arr_b[1]값이 같은 경우에도 각자의 값에서 부터시작하는 JLIS를 구하게 만들 수 있습니다.

 

코드