Informatica Online Judge

  k번째 최대증가부분수열 [0977 / 03D1]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 10   Total Tried : 16


The Champion of this Problem (C++) : coloredrabbit - 0ms / 1832byte
My Best Submission (C++) : N/A

[Algospot (JongMan) Data - JeongHJ]

Background

어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다.
단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다.

어떤 부분 수열이 단조 또는 증가할 때 이 부분 수열을 증가부분수열(increasing subsequence)라고 하며, 이 중 가장 긴 것을 최대증가부분수열(LIS, longest increasing subsequence) 라고 한다.

예를 들어, 5 20 21 22 8 9 10 의 최대 증가 부분 수열은 5 8 9 10 이다. 어떤 수열에는 LIS 가 두 개 이상 있을 수 있다. 예를 들어, 4 5 6 1 2 3 의 LIS 는 두 개가 있다. 모든 숫자가 서로 다른 (중복 숫자가 없는) 수열이 주어질 때, 이 수열의 LIS 중 사전 순서대로 맨 앞에서 k번째 있는 LIS를 출력하는 프로그램을 작성하시오.

Input

첫 줄에는 수열에 포함된 원소의 수 n (<= 500) 과 k의 정수가 입력된다. 그 다음 줄에 n개의 정수로 수열이 주어진다.

각 정수는 1 이상 100,000 이하이며, 같은 수는 두 번 나타나지 않는다.

[입력값의 정의역]
n <= 500

Output

첫 줄에는 LIS 의 길이 l 을 출력하고, 그 다음 줄에 l 개의 정수로 k번째 LIS 를 출력한다.

단, 조건을 만족하는 LIS가 없는 경우는 –1을 출력한다.

IO Example

입력
9 2
1 9 7 4 2 6 3 11 10

출력
4
1 2 3 11

입력2
4 2
1 2 3 4

출력2
-1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]