문제
풀이
11053번 가장 긴 증가하는 부분 수열이 왼쪽을 기준으로, 또 오른쪽을 기준으로 두 개가 진행되었다고 보면 쉽다. 즉, 11053번에서는 i번째에 해당하는 자릿수보다 자릿수, 값이 작은 수 중에서 dp값이 가장 큰 값에 +1 을 하였는데, 이를 왼쪽을 기준으로(원래처럼) 한 dp1과 오른쪽을 기준으로 한 dp2를 더하고 중복 덧셈된 1만큼 빼면 찾는 정답이 된다.
소스 코드
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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] = {0};
for(int i = 1; i<=N; i++){
scanf("%d", &map[i]);
}
int dp1[1001] = {0}; // 왼쪽을 기준으로 i번째 자릿수가 포함된 증가하는 가장 긴 부분 수열
int dp2[1001] = {0}; // 오른쪽을 기준으로 i번째 자릿수가 포함된 증가하는 가장 긴 부분 수열
// dp1 + dp2 - 1 이 가장 긴 바이토닉 부분 수열
dp1[1] = 1;
dp2[N] = 1;
for(int i = 2; i<=N; i++){
int result_max1 = 0;
for(int j = 1; j<i; j++){
if(map[i] > map[j]){
result_max1 = max(result_max1, dp1[j]);
}
}
dp1[i] = result_max1+1;
}
// 1~i-1번째 중에서 i번째 자리에 해당하는 수보다 작은 수 중의 dp값이 가장 큰 것 + 1이 dp1[i]의 값
for(int i = N-1; i>=1; i--){
int result_max2 = 0;
for(int j = N; j>i; j--){
if(map[i] > map[j]){
result_max2 = max(result_max2, dp2[j]);
}
}
dp2[i] = result_max2+1;
}
//N~i+1번째 중에서 i번째 자리에 해당하는 수보다 작은 수 중의 dp값이 가장 큰 것 + 1이 dp2[i]의 값
int result[1001] = {0};
for(int i = 1; i<=N; i++){
result[i] = dp1[i] + dp2[i];
}
sort(result, result+N+1, desc);
printf("%d\n", result[0] - 1);
}
