[11054] 가장 긴 바이토닉 수열

BOJ11054: 바이토닉 수열 - 가장 긴 바이토닉 부분 수열 구하기

---

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

설명

---

1. 문제 개요

• 입력된 수열에서 각 위치를 기준으로:
  1. 왼쪽 방향으로 증가하는 부분 수열을 계산한다.
  2. 오른쪽 방향으로 증가하는 부분 수열을 계산한다.
• 두 값을 합하여 가장 긴 바이토닉 부분 수열의 길이를 구한다.

---

2. 주요 변수와 데이터 구조

static int[] sq, dpr, dpl;

• sq: 원본 수열을 저장하는 배열.
• dpl: 각 위치에서 왼쪽 방향으로 증가하는 부분 수열의 길이를 저장하는 배열.
• dpr: 각 위치에서 오른쪽 방향으로 증가하는 부분 수열의 길이를 저장하는 배열.

---

3. 코드 동작 원리

1) 입력 처리 및 초기화:

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] input = br.readLine().split(" ");
sq = new int[n];
dpr = new int[n];
dpl = new int[n];
for (int i = 0; i < n; i++) {
    sq[i] = Integer.parseInt(input[i]);
}

• 입력받은 수열을 sq 배열에 저장한다.
• dpr과 dpl 배열을 0으로 초기화하여 동적 프로그래밍(DP) 계산에 사용한다.

2) 왼쪽과 오른쪽 증가 수열 계산:

for (int i = 0; i < n; i++) {
    order(i);    // i 위치 기준 왼쪽 증가 수열 계산
    reverse(i);  // i 위치 기준 오른쪽 증가 수열 계산
}

• order(i)는 dpl 값을 계산하며, i 위치를 포함한 왼쪽 방향 증가 수열의 최대 길이를 구한다.
• reverse(i)는 dpr 값을 계산하며, i 위치를 포함한 오른쪽 방향 증가 수열의 최대 길이를 구한다.

3) 가장 긴 바이토닉 부분 수열의 길이 계산:

int max = -1;
for (int i = 0; i < n; i++) {
    max = Math.max(max, dpl[i] + dpr[i]);
}
System.out.println(max - 1);

• 각 위치에서 dpl[i] + dpr[i]를 계산하여 바이토닉 수열의 길이를 구한다.
• 겹치는 중복 부분(i 위치)을 제거하기 위해 최종 길이에서 1을 뺀 값을 출력한다.

4) order와 reverse 함수 동작:

static int order(int num) {
    if (dpl[num] == 0) {
        dpl[num] = 1;
        for (int i = num - 1; i >= 0; i--) {
            if (sq[i] < sq[num]) {
                dpl[num] = Math.max(dpl[num], order(i) + 1);
            }
        }
    }
    return dpl[num];
}

static int reverse(int num) {
    if (dpr[num] == 0) {
        dpr[num] = 1;
        for (int i = num + 1; i < dpr.length; i++) {
            if (sq[i] < sq[num]) {
                dpr[num] = Math.max(dpr[num], reverse(i) + 1);
            }
        }
    }
    return dpr[num];
}

• order 함수: 현재 위치 num에서 시작해 왼쪽 방향으로 증가 수열의 최대 길이를 계산한다.
• reverse 함수: 현재 위치 num에서 시작해 오른쪽 방향으로 증가 수열의 최대 길이를 계산한다.
• 각 함수는 DP 배열(dpl/dpr)을 활용해 중복 계산을 방지하며, 재귀적으로 이전 값을 갱신한다.

정리

---

동적 프로그래밍(DP)을 활용해야 한다!

1. 왼쪽과 오른쪽 방향에서 증가 수열의 최대 길이를 계산하고,
2. 두 값을 합쳐 각 위치에서의 바이토닉 수열 길이를 구한다.