Game Develop

[Algorithm] Baekjoon 11054번 : 가장 긴 바이토닉 부분수열 본문

Algorithm/Baekjoon

[Algorithm] Baekjoon 11054번 : 가장 긴 바이토닉 부분수열

MaxLevel 2022. 12. 16. 21:36

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

 

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

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

www.acmicpc.net

 
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
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int inputs[1001= { 0 };
    int increaseDP[1001= { 0 };
    int decreaseDP[1001= { 0 };
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> inputs[i];
    }
 
    for (int i = 0; i < n; i++)
    {
        int maxNum = 0;
        increaseDP[i] = 1;
 
        for (int j = 0; j < i; j++)
        {
            if (inputs[j] < inputs[i])
            {
                maxNum = max(maxNum, increaseDP[j]);
            }
        }
 
        increaseDP[i] += maxNum;
    }
 
    for (int i = n-1; i >= 0; i--)
    {
        int maxNum = 0;
        decreaseDP[i] = 1;
 
        for (int j = n-1; j > i; j--)
        {
            if (inputs[j] < inputs[i])
            {
                maxNum = max(maxNum, decreaseDP[j]);
            }
        }
 
        decreaseDP[i] += maxNum;
    }
 
    int answer = 0;
 
    for (int i = 0; i < n; i++)
    {
        answer = max(answer, increaseDP[i] + decreaseDP[i] - 1);
    }
 
    cout << answer;
}
cs

 

증가했다가 내려가는 형태의 수열을 바이토닉 부분수열이라 한다.

각 인덱스마자 증가부분수열dp, 감소부분수열dp를 따로 테이블업데이트를 해 준 뒤,

마지막에 두 dp값을 더한값 중 큰 값을 출력하면 된다.

-1을 해주는 이유는 각 테이블에 업데이트할 때 기준인덱스자신을 포함한 값으로 업데이트 했기 때문이다.

테이블이 두개라서 자기자신이 두번포함됐기 때문에 -1을 해줘야 한다.