[99클럽/코딩테스트 챌린지/C++] 가장 긴 바이토닉 부분 수열 문제 해결

문제 링크 :

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

문제 개요

주어진 수열에서 특정 숫자를 기준으로 증가하다가 감소하는 바이토닉 수열의 부분 수열 중 가장 긴 수열의 길이를 구하는 문제입니다.

접근 방법

이 문제는 **DP(동적 계획법)**을 활용하여 해결합니다.

 

1. 문제 분할

바이토닉 수열은 두 가지 부분으로 나뉩니다:

1. 증가하는 부분 수열(LIS): 왼쪽에서 오른쪽으로 증가.
2. 감소하는 부분 수열(LDS): 오른쪽에서 왼쪽으로 감소.

2. 점화식

1. LIS[i]: 왼쪽에서 오른쪽으로 진행하며 A[i]를 포함한 가장 긴 증가 수열의 길이.
2. LDS[i]: 오른쪽에서 왼쪽으로 진행하며 A[i]를 포함한 가장 긴 감소 수열의 길이.

3. 바이토닉 수열 길이 계산

• dp[i]=LIS[i]+LDS[i]−1 (−1: A[i]가 LIS와 LDS에서 중복 계산됨을 제거.)

4. 결과

모든 dp[i]중 최대값이 가장 긴 바이토닉 수열의 길이가 됩니다.

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> list(N);
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }

    // LIS 계산
    vector<int> IncreaseDP(N, 1);
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < i; j++) {
            if (list[j] < list[i]) {
                IncreaseDP[i] = max(IncreaseDP[i], IncreaseDP[j] + 1);
            }
        }
    }

    // LDS 계산
    vector<int> DecreaseDP(N, 1);
    for (int i = N - 2; i >= 0; i--) {
        for (int j = N - 1; j > i; j--) {
            if (list[j] < list[i]) {
                DecreaseDP[i] = max(DecreaseDP[i], DecreaseDP[j] + 1);
            }
        }
    }

    // 바이토닉 수열 길이 계산
    vector<int> dp(N);
    for (int i = 0; i < N; i++) {
        dp[i] = IncreaseDP[i] + DecreaseDP[i] - 1;
    }

    // 결과 출력
    cout << *max_element(dp.begin(), dp.end()) << endl;

    return 0;
}

 

 

배운 점

1, LIS와 LDS의 활용:

• 증가 및 감소 부분 수열을 각각 계산하여 문제를 분할정복 방식으로 해결.

2, DP 배열의 의미:

• LIS[i]: A[i]를 포함한 가장 긴 증가 수열 길이.
• LDS[i]: A[i]를 포함한 가장 긴 감소 수열 길이.

3, 점화식 설계:

• 바이토닉 수열을 두 부분으로 나누어 계산하면 복잡한 문제를 간단히 해결 가능.

---

마무리

이번 문제를 통해 LIS와 LDS의 개념을 활용하여 복잡한 문제를 DP로 해결하는 방법을 학습했습니다.
특히, 문제를 단순화하여 접근하는 방법이 중요하다는 것을 다시 한번 깨달았습니다. 🚀