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

문제 링크

 

풀이

자세한 설명보다는 개념적으로 설명하겠습니다. { 1, 2, 1, 2, 3, 5, 4 }라는 수열로 예를 들겠습니다. d[i]는 i번째 요소를 마지막 수로 하는, 증가하는 수열의 길이로 하겠습니다. 인덱스는 1부터 하겠습니다. d[1]은 1이고 d[2]는 2입니다. d[3]은 1이고요 d[4]는 2, d[5]는 3, d[6]은 4, d[7]은 4입니다. d[i]는 i번째 요소보다 작은 요소 중에서 가장 큰 요소를 마지막 값으로 하는 수열의 길이에서 1을 더한 값이 됩니다. 예를 들어, 다섯 번째 요소가 3인데요, 이는 3보다 작은 수 중에 가장 큰 수인 2를 마지막 요소로 하는 수열의 길이에서 1을 더한 값이라는 거죠. 그니까 3보다 작은 d[i]의 최대값을 찾아 1을 더하면 됩니다.

 

코드

#include <cstdio>
int main()
{
	int d[1001] = {};
	int seq[1001] = {};
	int N;
	scanf("%d", &N);
	int max = 0;
	for (int i = 1; i <= N; ++i)
	{
		int prev = 0;
		scanf("%d", &seq[i]);
		for (int j = 1; j < i; ++j)
			if (seq[i] > seq[j])
				prev = prev < d[j] ? d[j] : prev;
		d[i] = prev + 1;
		max = max < d[i] ? d[i] : max;
	}
	printf("%d", max);
}