가장 긴 증가하는 부분 수열(LIS)

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

예제 입력 및 출력

입력

6

10 20 10 30 20 50

 

출력

4

소스 코드

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int N;
int cache[1001];
int sequence[1001];

int LIS(int idx) {
	//기저 사례
	if (cache[idx] != -1)
		return cache[idx];
	
	//함수탈출조건
	if (idx == N)
		return cache[idx] = 1;

	cache[idx] = 1;
	
	//재귀호출
	for (int i = idx + 1; i <= N; i++) {
		if (sequence[i] > sequence[idx])
			cache[idx] = max(cache[idx], 1 + LIS(i));
	}
	return cache[idx];
}

int main() {
	int length = 0;
	cin >> N;
	for (int i = 1; i <= N; i++)
		scanf("%d", &sequence[i]);

	memset(cache, -1, sizeof(cache));
	for (int i = 1; i <= N; i++)
		length = max(length, LIS(i));
	
	cout << length;
}

문제 풀이

 1. cache값 설정

• cache[num] : num번 idx로 시작하는 LIS의 길이 저장

 2. 함수 탈출 조건

• idx==N이면 가능한 수열의 원소가 1개밖에 없으므로 1 반환

 3. 재귀 호출

• idx+1 부터 N까지 수열의 원소 중 현재 원소보다 큰 수이면 LIS 함수를 재귀 호출

• 가장 큰 반환값 + 1을 현재 cache에 저장

 

문제 출처 : https://www.acmicpc.net/problem/11053