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

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

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

아이디어

1, LIS기초 문제

 

2, dp의 개념으로 시간 복잡도 O(n^2)로 풀이가 가능

 

3, 해당 배열의 숫자를 왼쪽부터 오른쪽으로 순회를 하면서 dp배열에 그 숫자가 들어갈 수 있는 최대 index를 구한다.

 

예시

5번째의 숫자의 최대 index값을 구하고자 하면  0~4까지의 dp배열을 순회하면서 5번째의 숫자보다 작은 숫자들에 대하여 dp값을 조사를 한 다음 가장 큰 수를 구하여 그 수의 +1을 한 만큼이 해당 숫자가 들어갈 수 있는 최대 위치이다.

 

소스코드

#include<cstdio>
using namespace std;

int num_arr[1001];
int dp[1001]; 

int main()
{
	int a;
	int res = -1;
	scanf("%d", &a);

	for (int i = 0; i < a; i++) {
		scanf("%d", &num_arr[i]);
	}


	//숫자를 조사
	for (int i = 0; i < a; i++) {
		int location = -1;

		//이미 조사한 위치들을 조사
		for (int j = 0; j < i; j++) {
			if (num_arr[j] < num_arr[i]) {
				if (location < dp[j]) {
					location = dp[j];
				}
			}
		}
		//dp값을 설정(위치를 배정)
		dp[i] = location + 1;

		if (res < dp[i]) {
			res = dp[i];
		}

	}

	printf("%d\n", res+1);

	return 0;
}