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

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

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

풀이과정

 

map[N]보다 작은 값 중 가장 긴 부분배열의 길이에 +1을 해준 값과 같다.

 

dp[N] = dp[X] + 1으로 점화식을 세웠다.

 

dp[X]란 map[N]보다 작은 값이면서 가장 부분배열의 길이다.

 

소스코드

#include <stdio.h>
#include <algorithm>
using namespace std;

int map[1001];
int dp[1001];
int N;
int solution(int n)
{
	int answer = 1;
	dp[0] = 1;
	for (int i = 1; i < n; i++) {
		dp[i] = 1;
		int num = 0;
		for (int j = i - 1; j >= 0; j--) {
			if (map[i] > map[j]) {
				num = max(num, dp[j]);
			}
		}
		dp[i] = num + 1;
		if (answer < dp[i]) {
			answer = dp[i];
		}
	}

	return answer;
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &map[i]);
	}
	printf("%d\n", solution(N));
	return 0;
}