백준 11053 - 가장 긴 증가하는 부분 수열 (C++)

문제

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

 

예시) A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

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

 

둘째 줄에는 수열 A를 이루고 있는 숫자들이 주어진다.

 

예제 입력

6
10 20 10 30 20 50

 

예제 출력

4

문제 해결

어디서 힌트를 얻을 수 있을까?

 

우선 '가장 긴'이라는 단어를 보고 이 문제는 최대 값을 구하는 문제라는 것을 알 수 있다.

 

이 문제를 쉽게 풀 수 없을까? 라는 생각을 해봤고 우선 브루트포스로 문제를 풀어보는 것을 생각해 보았다.

 

이 문제를 간단하게 브루트포스 알고리즘으로 구현하게 된다면 각 인덱스에서 시작해 가장 긴 증가하는 부분 수열을 구할 수 있다.

 

하지만 이렇게 문제를 풀게 되면 중복되는 부분 문제가 너무나도 많게 된다. 그러면 반드시 시간 초과가 될 것이다.

 

다음 예시를 보도록 하자.

 

A = {10, 20, 10, 30, 40, 50}

 

위의 예시를 봤을 때 0번 index에서 시작하는 부분 수열이나 2번 index에서 시작하는 부분 수열이나 뒤의 30, 40, 50은 똑같이 적용되는 부분 문제이다.

 

이런 경우 각 index에서 30, 40, 50은 중복되는 문제이고 이미 그 값을 한 번이라도 구했다면 굳이 다시 그 값을 구할 필요가 없게 된다.

 

즉, 메모이제이션 방법을 사용해서 문제를 풀 수가 있다.

 

코드

#include <iostream>

int arr[1002];
int cache[1002];

int dp(int idx, int N)
{
	int& ret = cache[idx + 1];
	if (ret != -1)
		return ret;
	ret = 1;
	for (int i = idx + 1; i < N; i++)
	{
		if (idx == -1 || arr[idx] < arr[i])
			ret = std::max(ret, dp(i, N) + 1);
	}
	return ret;
}

int main(void)
{
	int N;
	std::cin >> N;
	for (int i = 0; i < N; i++)
		std::cin >> arr[i];
	for (int i = 0; i <= N; i++)
		cache[i] = -1;
	std::cout << dp(-1, N) - 1 << std::endl;
	return 0;
}

 

문제 출처

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

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