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

 

수열의 어디서부터 출발해서 어떤 것을 골라야 가장 긴 증가하는 수열이 될까를 판단해야 한다.

이를 위해 위치별로 시작해보는 일도 필요하고, 해당 위치에서 가장 긴 수열은 무엇인지도 판단해야한다.

1. 정해진 위치에서 가장 긴 수열

2. 최적화

 

이 문제는 DFS로 접근했다.

예시의 경우로 보면, 10 20 10 30 20 50 의 index를 1, 2, 3, 4, 5, 6 으로 둔다.

그리고 index별로 차례대로 DFS를 수행하여 조건에 맞는 가장 긴 수열을 찾는다.

이 때도 길 찾기와 마찬가지로 분기별로 나뉘어서 수행하며 가장 길게 가는 수열을 찾아야 한다.

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int max = DFS(i, n,1);
		ans = ans > max ? ans : max;
		if (n - i <= ans) break;
	}
	printf("%d", ans);
}

메인함수에서는 입력받는 것과 DFS를 수행한 결과를 저장하는 역할을 한다.

 

수열의 길이가 최대 1000이기 때문에 DFS 로 앞에서 부터 들어가면 최대 O(N^2) 이 걸리게 되기 때문에 

부분적으로 최적화가 필요하다.

실제로 나는 그냥 DFS로 제출했을 때 시간 초과가 떴기 때문에 동적 계획법을 사용해 최적화를 시도했다.

 

int arr[1001];
int dp[1001];

int DFS(int idx,int n,int num) {
	if (dp[idx] >= num) {
		return dp[idx];
	}
	int max = 0;
	dp[idx] = num;
	if (idx == n - 1) {
		return num;
	}
	for (int i = idx + 1; i < n; i++) {
		if (arr[idx] < arr[i]) {
			int tmp = DFS(i, n, num + 1);
			max = max > tmp ? max : tmp;
		}
	}
	return max;
}

여기서 i는 항상 오른쪽으로 이동하면서 비교하기 때문에 앞서서 세었던 녀석을 다시 셀 필요가 없다.

dp라는 배열을 하나 더 선언하여 해당 위치에서 가장 길었을 때의 길이를 저장해둔다.

만약 내가 시도해보려는 숫자가 과거에 더 길었던 적이 있었다면

앞으로 어떻게 위치를 옮기던 과거보다 길어질 수는 없기 때문에 DFS를 종료한다.

 

실행 방식은 다음 그림과 같다.

전체코드

#include <stdio.h>

int arr[1001];
int dp[1001];

int DFS(int idx,int n,int num) {
	if (dp[idx] >= num) {
		return dp[idx];
	}
	int max = 0;
	dp[idx] = num;
	if (idx == n - 1) {
		return num;
	}
	for (int i = idx + 1; i < n; i++) {
		if (arr[idx] < arr[i]) {
			int tmp = DFS(i, n, num + 1);
			max = max > tmp ? max : tmp;
		}
	}
	return max;
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int max = DFS(i, n,1);
		ans = ans > max ? ans : max;
		if (n - i <= ans) break;
	}
	printf("%d", ans);
}