[종만북]9.동적 계획법 테크닉-K번째 증가 수열

문제

출처 : https://www.algospot.com/judge/problem/read/KILS

어떤 정수 수열에서 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 를 출력하는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어진다. 각 테스트 케이스의 첫 줄에는 수열에 포함된 원소의 수 N (<= 500) 과 K 가 주어진다. K 는 32비트 부호 있는 정수에 저장할 수 있다. 그 다음 줄에 N개의 정수로 수열이 주어진다. 각 정수는 1 이상 100,000 이하이며, 같은 수는 두 번 등장하지 않는다.

주어진 수열의 LIS 는 최소 K 개 있다고 가정해도 좋다.

출력

각 테스트케이스마다 두 줄을 출력한다. 첫 줄에는 LIS 의 길이 L 을 출력하고, 그 다음 줄에 L 개의 정수로 K번째 LIS 를 출력한다.

풀이(책 참고)

먼저 기존에 풀었던 LIS를 구하는 메소드는 다음과 같다.

static int LIS(int start) {
		int ret = cache[start + 1];
		if (ret != 0)
			return ret;
		ret = cache[start + 1] = 1;
		for (int next = start + 1; next < n; next++) {
			if (start == -1 || A[start] < A[next]) {
				ret = Math.max(ret, LIS(next) + 1);
				cache[start + 1] = ret;
			}
		}
		return ret;

	}

K번째 문제를 풀기 위해 일정 답을 건너뛰어야 하는데, 여기서는 정렬된 LIS들 중 일정 개수만큼 건너뛰는 원리로 구현하여야 하므로, 각 LIS의 길이를 알아야 한다. 즉, 시작 인덱스가 start에서 시작하는 LIS의 수를 찾는 메서드를 구현한다. start 인덱스 다음부터 LIS들을 찾아 길이를 계산할 때, 다음 인덱스 이후가 현재 인덱스와 LIS로 이어질 조건은 위 LIS를 찾는 조건과같이 A[start]<A[next]이며, LIS(start)와 LIS(next)+1이 같아야 한다. 즉, 다음 인덱스의 배열값이 크다는 전제하에 다음 인덱스의 LIS길이가 현재 LIS길이보다 1보다 작다는 것은 두 인덱스가 이어져 LIS를 형성한다는 것을 의미하므로, 이때의 개수를 누적할 수 있다.

// A[start]에서 시작하는 LIS의 수
	static double count(int start) {
		if (LIS(start) == 1)
			return 1;
		double ret = cache2[start + 1];
		if (ret != -1)
			return ret;
		ret = cache2[start + 1] = 0;
		for (int next = start + 1; next < n; next++) {
			if ((start == -1 || A[start] < A[next]) && LIS(start) == LIS(next) + 1) {
				ret = cache2[start + 1] = Math.min(MAX, ret + count(next));
                // 오버플로를 막기 위해 20억이상의 수는 20억으로 처리
			}
		}
		return ret;
	}

LIS 메서드와 유사하게 메모이제이션을 적용하였고, 기저 사례로 현재 인덱스로부터 시작하는 LIS의 길이가 1인 경우를 1로 리턴하도록 설정하였다. 이후 반복문은 위의 조건을 만족시키는 다음 인덱스를 찾아 해당 값을 재귀호출하여 누적시키도록 하였다. 따라서 start에서 시작하는 LIS의 수를 찾아 리턴할 수 있다.

이를 통해 건너뛰는 과정을 구현할 수 있는데, 먼저 건너뛰어야할 수 skip을 k-1로 정의한다. 그리고 특정 인덱스 start에서 시작하여 skip개를 건너뛴 수열을 찾는다고 할 때, 위의 개수를 셀따와 마찬가지로 start 이후 인덱스들 중 A[start]<A[next]와 LIS(start)==LIS(next)+1을 만족시키는 인덱스가 다음 LIS 성분 후보일 수 있다. 여기서, 이 LIS 후보들 중 건너뛸 개수만큼 뺄때 중요한 것은 해당 A[next] 값들이 오름차순으로 정렬하여야 비교할 수 있다는 것이다. 예를 들어, 현재 배열값이 1이고 위 조건을 만족시키는 다음 LIS 후보들의 배열값이 4, 2, 5, 7이라 할 때, 각각의 이어진 LIS들은 (1,4…), (1,2…),(1,5…),(1,7…)으로 형성될 것이다. 따라서 먼저 이러한 배열값들을 정렬시켜야 건너뛰는 단계로 넘어갈 수 있기 때문에 후보들을 모아 저장하고, 이를 정렬시켜야 한다.

정렬이 완료됬으면, 이후 배열값들을 크기순으로 돌며 위에서 정의한 count 메서드를 통해 각 인덱스의 LIS 개수를 카운팅한다. 이 때, 카운팅된 값이 skip값보다 작거나 같은 경우 k번째 lis는 해당 인덱스 이후 범위에 존재한다는 것을 의미하므로 skip값에서 해당 카운팅한값만큼 건너뛸수 있음을 의미하므로, 값을 빼고, 만약 카운팅한 값이 큰경우는 해당 인덱스로 시작하는 LIS가 k번째 LIS에 속한다는 것을 의미하므로 해당 인덱스를 다음 인덱스값으로 삼아서 재귀호출을 통해 수열값을 찾아나가면 된다.

// A[start]에서 시작하는 LIS중 사전순으로 skip개 건너뛴 수열을 lis에 저장함
// pair-> 클래스로 구현, PiarComparator->Comparator 구현을 통한 Collections.sort 수행
static void reconstruct(int start, int skip, Vector<Integer> lis) {
		if(start!=-1)
			lis.add(A[start]);
		Vector<Pair> followers = new Vector<Pair>();
		for(int next=start+1;next<n;next++) {
			if((start==-1||A[start]<A[next])&&LIS(start)==LIS(next)+1)
				followers.add(new Pair(A[next],next));
		}
		Collections.sort(followers,new PairComparator());
		for(int i=0;i<followers.size();i++) {
			int idx = followers.get(i).value;
			double cnt = count(idx);
			if(cnt<=skip)
				skip-=cnt;
			else {
				reconstruct(idx, skip, lis);
				break;
			}
		}
	}

매개변수에 Vector 클래스로 int값을 저장하는 lis가 있는데, 이는 재귀호출에 따라 찾은 k번째 LIS의 각각 요소값들을 저장하기 위한 클래스이다. 또한, 앞서 설명한 바와 같이 다음 LIS후보들을 정렬하여야 하므로, LIS후보를 만족하는 배열값과 이때의 인덱스를 Pair 클래스에 저장하여 Vector에 모으도록 하며(Pair 클래스는 별도 구현), 이렇게 후보를 만족하는 Pair들을 정렬시켜 순서대로 count메소드를 호출하여 건너뛰도록 구현하였다.

Menu

문제

입력

출력

풀이(책 참고)