알고스팟 최대 증가 부분 수열 LIS

https://algospot.com/judge/problem/read/LIS

algospot.com :: LIS

 

 

<접근방법>

dp도 완전탐색을 해줘야합니다.

그럼 1 2 3 4 5 가 있다고 가정해봅시다.

1에서 5까지의 LIS를 구하고 2에서 5까지의 LIS를 구하고... 쭉 다 탐색해주면 되겠죠.

이때 중복부분이 발생한다는 것을 알 수 있죠.

(1 2 3 4 5 와 2 3 4 5)

이 중복부분을 메모이제이션을 하면서 완전탐색을 하도록 합시다.

 

lis()는 a[start]부터 시작하는 부분 수열에서 최대 증가 부분 수열의 길이를 출력하는 함수 입니다.

 

 

---

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;

int tc, n;
int a[500], cache[500];

int lis(int start) {
	//중복방문
	int &res = cache[start];
	if (res != -1) return res;

	//계산
	res = 1;
	for (int next = start+1; next < n; next++) {
		if (a[start] < a[next]) {
			res = max(res, make(next)+1);
		}
	}
	
	//리턴
	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> tc;
	while (tc--) {
		memset(cache, -1, sizeof(cache));

		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}

		int res = 1;
		for (int i = 0; i < n; i++) {
			res = max(lis(i), res);
		}
		cout << res << '\n';
	}

	return 0;
}

 

조금 더 간결화하면

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
using namespace std;

int tc, n;
int cache[501], arr[501];

int lis(int start) {
	//기저사례
	
	//중복방문
	int &res = cache[start+1];
	if (res != -1) return res;

	//계산
	res = 1;
	for (int next = start+1; next < n; next++) {
		if (start == -1 || arr[start] < arr[next]) {
			res = max(res, lis(next)+1);
		}
	}

	//리턴
	return res;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> tc;
	while (tc--) {
		memset(cache, -1, sizeof(cache));

		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
		}

		cout << lis(-1)-1 << '\n';
	}

	return 0;
}

 

부분 수열의 시작점을 for문으로 해결해서 간결화 시킨 것입니다.

이것을 위해 start를 -1로 시작을 합니다. 그래서 a[start]의 lis의 길이는 cache[start+1]에 대응이 됩니다.

(제대로 이해를 한 것인지 모르겠으나 맞다면 정말 깨름칙합니다)

 

 

---

 

 

<느낀 점>

dp 접근법

1. dp는 완전탐색이다.

2. 이걸 재귀로 구현할 것이다.

3. 재귀함수의 입출력을 명확히 정의한다.

  - 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꾼다.

  - 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄입니다. 

 

 

 

 

 

[참고]

-프로그래밍 대회에서 배우는 알고리즘 해결전략1