반응형

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

 

11054번: 가장 긴 바이토닉 부분 수열

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

가장 긴 증가하는 부분 수열을 구하는 문제를 풀어보고 풀어보시기를 추천드립니다!

 

먼저 각 idx의 증가하는 부분 수열 길이의 최댓값을 increase 배열에 lower_bound를 활용하여 저장해줍니다. 마찬가지로 감소하는 부분 수열은 배열의 끝부분에서부터 시작하여 부분 수열 길이의 최댓값을 decrease 배열에 lower_bound를 활용하여 저장해줍니다.

 

다음으로 0번째 idx부터 N-1번째 idx까지 increase 배열과 decrease 배열을 더한 값에 -1을 해준 후 최댓값을 max에 저장해준 뒤 출력하면 답을 쉽게 구할 수 있습니다.

 

-1을 해주는 이유는 특정 idx에서 increase 배열과 decrease 배열이 한번 겹치기 때문입니다.

 

 

[ 소스 코드 ]

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int arr[1000];
int increase[1000];
int decrease[1000];
vector<int> mem;
 
int N;
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    int max = 1;
 
    for (int i = 0; i < N; i++) {        //증가하는 부분 수열의 최대 길이 increase에 저장
        if (i == 0) {
            mem.push_back(arr[i]);
        }
        else {
            if (mem[mem.size() - 1] < arr[i]) {
                max++;
                mem.push_back(arr[i]);
            }
            else {
                int idx = lower_bound(mem.begin(), mem.end(), arr[i]) - mem.begin();
                mem[idx] = arr[i];
            }
        }
        increase[i] = max;
    }
 
    max = 1;
    mem.clear();
 
    for (int i = N-1; i >= 0; i--) {    //감소하는 부분 수열의 최대 길이 decrease에 저장
        if (i == N-1) {
            mem.push_back(arr[i]);
        }
        else {
            if (mem[mem.size() - 1] < arr[i]) {
                max++;
                mem.push_back(arr[i]);
            }
            else {
                int idx = lower_bound(mem.begin(), mem.end(), arr[i]) - mem.begin();
                mem[idx] = arr[i];
            }
        }
        decrease[i] = max;
    }
 
    max = 0;
 
    for (int i = 0; i < N; i++) {        //한 점에서 증가 수열과 감소 수열의 수가 하나 겹치므로 -1을 해줌
        if (max < increase[i] + decrease[i] - 1) {
            max = increase[i] + decrease[i] - 1;    //최댓값 저장
        }
    }
 
    cout << max;
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 9663번 - N-Queen (C++)  (0) 2022.06.07
[ 백준 ] 1504번 - 특정한 최단 경로 (C++)  (0) 2022.06.06
[ 백준 ] 11779번 - 최소비용 구하기 2 (C++)  (0) 2022.06.04
[ 백준 ] 17070번 - 파이프 옮기기 1 (C++)  (0) 2022.06.03
[ 백준 ] 9251번 - LCS (C++)  (0) 2022.06.02

+ Recent posts

티스토리툴바