백준 11053 가장 긴 수열 -C언어

 

11053 가장 긴 수열을 구하는 문제이다.

나는 이 문제를 이해하는데 많은 시간이 들었다. 어렵다.

 

이 문제의 핵심은 3가지라고 생각한다.

 

1. dp문제라는 것을 생각하기.

2. 이전 input값 보다 현재 input값이 더 큰가?

3. input값이 더 크다면 최대 수열의 길이는 더 큰가?

 

 

 

#include<stdio.h>

int my_max(int a, int b) {
	return a > b ? a : b;
}

int main() {

	int n, i, j, max;
	int arr[1001];
	int memo[1001];

	scanf_s("%d", &n);
	max = 1;
	arr[0] = 0;
	memo[0] = 0;

	for (i = 1; i <= n; ++i) {
		scanf_s("%d", &arr[i]);
		memo[i] = 1;//자기 자신도 길이이므로 기본 값 1

		for (j = 1; j < i; j++) {
			if (arr[i] > arr[j])//들어간 input값이 이전의 것 보다 큼?
				memo[i] = my_max(memo[i], memo[j] + 1);//최대 수열은 뭐가 더 큼?
		//dp사용부분
		}

		if (max < memo[i])
			max = memo[i];
	}//max가 가장 긴 수열

	printf("%d\n", max);

	return 0;


}