[C++] 백준 11054 가장 긴 바이토닉 부분수열

문제 풀이

가장 긴 바이토닉 부분 수열은 증가하는 부분수열과 감소하는 부분 수열을 합친 것(?) 중에 가장 긴 것을
구하는 것이므로
가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열을 합친 문제다.

1) 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053
2) 가장 긴 감소하는 부분수열
https://www.acmicpc.net/problem/11722

 

 

가장 긴 증가하는 부분 수열은 아래의 포스트에 설명되있다.
https://deonggideok.tistory.com/25

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

가장 긴 감소하는 부분 수열은 가장 긴 증가하는 부분 수열을 구하는 것과 큰 차이가 없다.

두 개의 for문을 이용해서 현재 인덱스가 가리키는 숫자를 포함한 가장 긴 감소하는 부분 수열을 구하는 것은 같다.
하지만, 감소하는 부분 수열을 구할 때는 인덱스를 뒤에서 부터 접근한다.
그 과정은 아래와 같다.

 

 

1) 바깥의 for문
바깥의 for문에서는 숫자들의 나열이 담긴 배열에서 맨 끝 인덱스부터 시작해 인덱스를 하나하나 감소시킨다.
이를 통해 배열 중 숫자를 하나 지정해 아래의 for문에서 사용한다.
지정한 배열의 숫자를 지정된 숫자라고 하자.

 

 

2) 안의 for문
안의 for문에서는 지정된 숫자를 포함하는 가장 긴 감소하는 부분수열의 길이를 구한다.
for문에서 숫자들의 나열이 담긴 배열에서 맨 마지막 숫자부터 지정된 숫자 전까지 접근한다.
접근한 원소가 지정된 숫자보다 작은 경우

• 지정된 숫자를 포함해 새로운 가장 긴 감소하는 부분 수열을 만들 수 있으므로
• 지정된 숫자 이전의 감소하는 부분 수열 길이 중 가장 큰 것을 구하고 거기에 +1하면
• 지정된 숫자를 포함한 가장 긴 감소하는 부분 수열의 길이를 구할 수 있다.

3) 다시 바깥의 for문
2)의 과정을 통해 구한
지정된 원소까지의 LIS 길이를 갱신한다.

 

 

증가하는, 감소하는 부분 수열의 길이에 대한 DP 수행 결과를 얻으면
새로운 for문을 이용해 인덱스를 처음부터 끝까지 증가시켜가며
증가하는 부분 수열의 길이와 감소하는 부분 수열의 길이의 합이 가장 큰 것을 찾는다.
이 값은 인덱스에 해당하는 원소가 2번 카운트 되었으므로 1을 뺀 값이
가장 긴 바이토닉 부분 수열의 길이 값이다.

코드

#include <iostream>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int arr[1001];
    int dp1[1001] = { 0 }; // 가장 긴 증가하는 부분수열 길이
    int dp2[1001] = { 0 }; // 가장 긴 감소하는 부분수열 길이
 
    // 숫자 배열 입력
    for (int i = 0; i < n; i++) 
        cin >> arr[i];
 
    // 가장 긴 증가하는 부분 수열 구하기
    for (int i = 0; i < n; i++) {
        int maxDP = 0; // 현재 숫자를 포함한 가장 긴 증가하는 부분수열 길이
        for (int j = 0; j < i; j++) { 
            if (arr[j] < arr[i]) { // 증가하는 부분 수열이 가능 한 경우
                if (maxDP < dp1[j]) 
                    maxDP = dp1[j]; // 현재 숫자를 포함한 증가하는 부분수열 길이 갱신
            }
        }
        dp1[i] = maxDP + 1; // 현재 숫자를 포함해야 하므로 + 1
    }
 
    // 가장 긴 감소하는 부분 수열 구하기
    for (int i = n - 1; i >= 0; i--) {
        int maxDP = 0; // 현재 숫자를 포함한 가장 긴 감소하는 부분수열 길이
        for (int j = n - 1; j > i; j--) { 
            if (arr[j] < arr[i]) { // 감소하는 부분 수열이 가능 한 경우
                if (maxDP < dp2[j]) 
                    maxDP = dp2[j]; // 현재 숫자를 포함한 감소하는 부분수열 길이
            }
        }
        dp2[i] = maxDP + 1; // 현재 숫자를 포함해야 하므로 + 1
    }
 
    int max = 0; // 가장 긴 증가하는 부분수열 길이
    for(int i = 0; i < n; i++){
        if(dp1[i] + dp2[i] > max) max = dp1[i] + dp2[i];
    }
 
    max -= 1; // 중복된 길이 1 제거
 
    // 결과 출력
    cout << max <<'\n';
}