1388 : 합친 부분 수열의 LIS
제한시간: 1000 ms
메모리제한: 64 MB
해결횟수: 57 회
시도횟수: 368 회
S가 정수의 수열이라고 할 때, LIS(최장 증가 부분수열)이란 S에서 몇 개의 원소를 제거한 다음, 나오게 되는 부분수열이 오름차순(작은 순서에서 큰 순서대로, 같은 건 존재하지 않는다.)으로 나오는 부분수열 중 가장 긴 수열을 말한다.
예를 들어 S={1, 3, 2, 7, 3, 6}의 LIS={1, 2, 3, 6}이 된다.
A와 B의 정수의 수열이 주어질 경우, 2개를 합쳐서 LIS를 구해보고자 한다. 여기서 2개의 수열을 합친다는 것은 하나의 수열이 자리잡은 상태에서 다른 수열의 원소들이 그 사이사이에 배치하는 것을 말한다. 추가되는 수열의 하나의 원소는 자리잡은 수열에 한번만 들어갈 수 있으며, 어디에 들어가도 상관없으나, 원래의 순서가 바뀌어서는 안 된다. 다시 말해서 2개의 수열을 합칠때는 각 수열의 원소끼리는 원래의 순서를 유지하면서 두 수열의 원소를 임의의 위치에 배치할 수 있다는 말이다.
만약 {2, 1}, {3, 4} 라는 두개의 수열이 있을 경우 {3, 4, 2, 1}은 합친 부분 수열이 될 수 있으며, {1, 3, 4} 역시 가능하나, {1, 2, 3, 4}의 경우 불가능하다.
합친 부분 수열의 LIS를 구해보자.
첫 번째 줄에는 A와 B의 원소의 개수 N, M이 입력되며 이는 100을 넘지 않는다. 그 다음 줄에는 A의 원소 N개가 순서대로 입력된다. 그리고 마지막 줄에는 B의 원소 M개가 순서대로 입력된다. A,B의 원소는 int범위 이내이다.
입력에 대해서 A와 B를 합친 부분 수열의 LIS의 길이를 출력한다.
2 2 1 2 3 4 |
4 |
5 5 1 7 3 8 5 1 9 3 10 5 |
5 |