[c++] 알고리즘 문제 해결 전략 1권 :: JLIS (코드 x - 알고리즘 분석만)

합친 LIS

https://www.algospot.com/judge/problem/read/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 의 길이를 출력합니다.

예제 입력

3
3 3
1 2 4
3 4 7
3 3
1 2 3
4 5 6
5 3
10 20 30 1 2
10 20 30

예제 출력

5
6
5

나의 답

1. 최대 증가 수열을 구해서 조합

   시간도 오래걸리고 마지막 예제를 통과하지 못한다.

   각 수열의 LIS라고 해서 JLIS의 요소가 되는 것은 아님

책의 답

 책의 답이 헷갈려서 한참을 생각했다. 거꾸로 생각하면 이해하기 쉽다. 먼저 (a) 그림처럼 마지막 요소들에 포인터를 대고 있다면 2, 30 두 개를 이용한 LCS가 나와서 길이는 2일 것이다. (두 수가 같다면 1이겠지만 두 수가 같을 경우를 배제하고 생각하기로 했으므로 항상 2가 나온다.) 그 다음 A나 B 둘 중 하나의 포인터를 앞으로 당긴다. 그 때 수가 감소한다면 요소의 갯수가 하나 늘어난다. (포인터가 앞에서 오는 연산에서 증가수열만을 취하는 것과 같은 의미이다.)

 따라서 (c) 그림을 보면 포인터가 30,30을 가리키고 있을 때 A의 포인터가 감소한것이 아니라 증가했으므로 뒤의 것은 신경쓰지 않는다. 그리고 위의 그림에서는 원래 1개의 요소를 갖지만 같은 노드는 고려하지 않겠다 했으므로 아래의 그림처럼 2개의 노드를 갖는 형태가 된다.

 이를 앞에서부터 포인터가 가는 것으로 표현해보면, 모든 포인터의 위치를 조사하면서 현재 포인터 위치부터 A의 포인터를 움직여서 증가수열동안 조사하고 B의 포인터를 움직여서 증가수열동안 조사하는 식으로 반복한다.

 

이걸 어떻게 생각해낼까.. 후 ... 아직 멀었다.