[C++] 백준 11053번: 가장 긴 증가하는 부분 수열

문제 바로가기

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

---

다이나믹 프로그래밍 분류의 문제를 풀다보면 어떤 문제는 금방 풀리고, 어떤 문제는 아무리 생각해보 답이 떠오르지 않는다. 이 문제는 후자에 해당했다. 첫 풀이는 간단했다. 첫 번째 요소부터 시작해서 뒤에 이어지는 값 중 자신보다 큰 값들의 개수를 출력했다. 당현하게도 이는 정답이 아니다. 자신보다 큰 수는 맞지만, 이어지는 수 보다도 큰 수가 선택 돼야 하기 때문이다. 그래서 깊이 우선 탐색을 활용하기로 했다. 모든 분기를 거쳐 확인해 보는 것이다. 이전에 선택된 값보다 큰 값이면 재귀호출을 통해 분기를 나눠 탐색한다. 이 경우 정확한 답이 도출됐지만, 수 많은 중복 연산이 발생하여 지나치게 많은 시간이 소요된다.

결국 구글 검색을 통해 답안을 확인했다. 다이나믹 프로그래밍 문제 답게 풀이는 간단했다. A의 i번째 요소까지의 최대 길이를 활용하는 것이다. 새로운 배열 DP를 하나 선언하여, 배열의 i번째 요소에 A의 i번째 요소까지의 최대 길이를 저장하고 i + 1번째 요소에는 그 이전 중 A[i + 1]보다 작은 A[j] 중 가장 큰 DP[j]를 찾고 1을 더한 값을 저장하면 된다. 이를 N번째까지 마치고 배열 DP 중 최대값을 출력하면 끝.

---

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; i++)
#define INF 987654321
#define EL "\n"

int main() {
	FAST_IO;
	
	int N;
	cin >> N;

	int A[1000]{};
	FOR(i, N)
		cin >> A[i];

	int DP[1000]{};
	FOR(i, N) {
		int max_length = 0;
		FOR(j, i)
			if(A[j] < A[i])
				if (DP[j] > max_length)
					max_length = DP[j];
		DP[i] = max_length + 1;
	}

	int length = 0;
	FOR(i, N)
		if (DP[i] > length)
			length = DP[i];

	cout << length << EL;

	return 0;
}