백준 11053 가장 긴 증가하는 부분 수열 (c++) : 피너클

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

dp를 이용하는 문제다.

dp란 계산한 내용을 저장한뒤 다음에 필요로 할때 꺼내 사용하는 알고리즘이다.

 

solve함수를 지정해 문제를 해결할것이다.

solve함수는 현재 위치를 나타내는 now와 마지막으로 추가한 수를 나타내는 last를 전달받는다.

10

20

10

30

20

50

solve함수를 현재 위치의 배열을 추가할것인지 추가하지 않을 것인지를 고른다. 만약 10을 추가한다면

10

20

10

30

20

50

현재위치는 10 다음인 20의 위치로 변하고 last는 10으로 변한다. 만약 10을 추가하지 않으면

10

20

10

30

20

50

현재위치는 10의 다음인 20의 위치로 변하고 last는 변하지 않는다.

int ans = solve(now + 1, last);

현재 위치의 배열을 추가하지 않고 넘어가면 now+1과 last를 전달한다.

if (arr[now] > last) ans = max(ans, solve(now + 1, arr[now]) + 1);

만약 현재 위치의 배열이 last보다 크다면 현재 위치를 추가할수 있다.

ans에는 현재 위치를 추가하지 않은 solve가 들어가 있으니 현재 위치를 추가한 solve와 비교해 더 큰수를 ans에 넣는다.

if (now == n - 1) {
	if (last < arr[now]) return 1; 
	else return 0; 
}

만약 현재 위치가 n-1이라면 (배열의 끝이라면)

arr[now]가 last보다 크다면 현재 배열을 추가할것이니 1을 반환하고

arr[now]가 last보다 작다면 추가하지 못하니 0을 반환한다.

int &ret = cache[now][last];
if (ret != -1) return ret;

int &ret은 cache[now][last]의 주소값을 받아 cache[now][last]와 같은 곳을 가르키게된다.

먄약 ret의 값을 바꾸면 cache[now][last]의 값도 바뀌는 것이다.

만약 ret의 값이 -1이 아니면 (시작하자마자 모든 cache에 -1을 할당한다) 그대고 ret을 반환한다.

-1이 아니라는 뜻은 이미 solve(now, last)를 지나갔다는 뜻이다.

return ret = ans;

마지막에 return과 함께 ret에 ans를 할당함으로써 ret의 없데이트와 반환을 동시에 한다.

 

이해를 위해 순서를 뒤섞어놨지만 전체코드를 보는데 큰 어려움을 없을것이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <queue>

using namespace std;

int n;
int arr[1001];
int cache[1001][1001];
bool chk[1001];

int solve(int now, int last) {
	if (now == n - 1) {
		if (last < arr[now]) return 1; 
		else return 0; 
	}
	int &ret = cache[now][last];
	if (ret != -1) return ret;
	int ans = solve(now + 1, last);
	if (arr[now] > last) ans = max(ans, solve(now + 1, arr[now]) + 1);

	return ret = ans;
}

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

	memset(cache, -1, sizeof(cache));

	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	cout << solve(0, 0) << endl;
}

전체코드다.