합친 부분 수열의 LIS > 문제은행

본문 바로가기


실전대비 Level4

1388 : 합친 부분 수열의 LIS

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 19 회    시도횟수: 96 회   



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의 길이를 출력한다.


[Copy]
2 2
1 2
3 4
[Copy]
4


[Copy]
5 5
1 7 3 8 5
1 9 3 10 5
[Copy]
5




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.