문제
풀이
dp[n] : n번째 자리 수를 포함한 부분 수열 중 최장 길이이다. 그래서 dp[n] 은 1~n-1번째에 해당하는 수 중 n번째에 해당하는 수보다 작은 수에서 가장 큰 dp값 + 1이 dp[n]의 값이 될 것이다. 그렇게 n번째 자리까지의 dp값 중 가장 큰 값이 최종 정답이 된다. 예를 들어, A = {10, 20, 10, 30, 20, 50}에서 dp[1] = 1(10)인데, 이는 1번째 자릿수보다 작은 값이 그 아래 자릿수에 없으므로 1이 되고, dp[2] = 2(10, 20)는 2번째 자릿수보다 작은 값 1이 dp[1] = 1이므로 여기에 2번재 자릿수인 2를 이어 붙여서 결과적으로 +1을 한 dp[2] = 2가 되고, dp[3] = 1(10)인데 3번재 자리에 해당하는 값인 1보다 작은 수는 없으므로 1이 되며, dp[4]는 4번째 자릿수인 30보다 작은 10, 20, 10 중 dp 값이 가장 큰 dp[2] = 2에 30을 이어 붙인 dp[4] = 3이 되는 것이다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>
using namespace std;
int desc(int a, int b){
return a>b;
}
int main(){
int N;
scanf("%d", &N);
int map[1001];
int dp[1000];
for(int i = 1 ; i<=N; i++){
scanf("%d", &map[i]);
}
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i<=N; i++){
int result_max = 0;
for(int j = 1; j<=i-1; j++){
if(map[i] > map[j]){
result_max = max(result_max, dp[j]);
}
}
dp[i] = result_max + 1;
}
sort(dp, dp+N+1, desc);
printf("%d\n", dp[0]);
}
