백준 11054번 [가장 긴 바이토닉 부분 수열](C++)-yes6686- 티스토리

백준 문제 풀이: 11054 [가장 긴 바이토닉 부분 수열]

---

문제 링크: https://www.acmicpc.net/problem/11054

문제 설명:

바이토닉 수열은 부분 수열의 길이가 증가했다가 감소하는 특징을 가집니다. 주어진 배열에서 가장 긴 바이토닉 부분 수열의 길이를 구하는 문제입니다.

입력:

• 첫째 줄에 배열의 크기 n이 주어집니다. (1 ≤ n ≤ 1,000)
• 둘째 줄에 배열의 원소가 주어집니다. (1 ≤ 원소 값 ≤ 1,000)

출력:

• 가장 긴 바이토닉 부분 수열의 길이를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int arr[1001];
int inc[1001]; // 증가 부분 수열
int dec[1001]; // 감소 부분 수열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 증가 부분 수열 계산
    for (int i = 0; i < n; i++) {
        inc[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                inc[i] = max(inc[i], inc[j] + 1);
            }
        }
    }

    // 감소 부분 수열 계산
    for (int i = n - 1; i >= 0; i--) {
        dec[i] = 1;
        for (int j = n - 1; j > i; j--) {
            if (arr[j] < arr[i]) {
                dec[i] = max(dec[i], dec[j] + 1);
            }
        }
    }

    // 가장 긴 바이토닉 부분 수열 계산
    int maxLength = 0;
    for (int i = 0; i < n; i++) {
        maxLength = max(maxLength, inc[i] + dec[i] - 1); // 중복된 i를 제거하기 위해 -1
    }

    cout << maxLength << '\n';
    return 0;
}

예제

입력:
10
1 5 2 1 4 3 4 5 2 1

출력:
7

입력:
5
10 20 30 20 10

출력:
5

---

코드 설명

• 증가 부분 수열:
  • 배열의 각 원소를 기준으로, 앞선 원소들 중 자신보다 작은 값을 찾고, 증가 부분 수열의 길이를 갱신합니다.
• 감소 부분 수열:
  • 배열의 각 원소를 기준으로, 뒷부분에서 자신보다 작은 값을 찾고, 감소 부분 수열의 길이를 갱신합니다.
• 바이토닉 수열:
  • 증가 부분 수열과 감소 부분 수열의 합에서 중복된 기준 원소를 제외한 값을 계산합니다.

시간 복잡도

• 증가 부분 수열 계산: O(n²)
• 감소 부분 수열 계산: O(n²)
• 최종 계산: O(n)
• 전체 시간 복잡도: O(n²)

---

결과

코드는 가장 긴 바이토닉 부분 수열의 길이를 정확히 계산하며, 동적 프로그래밍을 활용해 효율적인 풀이를 제공합니다. 배열 크기가 최대 1,000까지이므로 실행 시간이 적절합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!