문제

---

이해

---

바이토닉 수열은 문제처럼 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN 을 만족하는 수열을 의미한다.

다시말해 기준이 되는 정점까지는 오름차순으로 정렬되고 정점을 지난 뒤에는 내림차순으로 정렬된 수열이다.

수열이 주어졌을 때 해당 수열에서 만들 수 있는 부분 수열 중 가장 긴 바이토닉 수열의 길이를 출력하라.

접근

---

DP를 어떻게 세울지 고민하다가 이전에 풀었던 11053번 가장 긴 증가하는 부분 수열 문제가 떠올랐다.

해당 문제에서는 DP를 1차원 배열로 설정하고 DP[i]를 마지막이 i번인 가장 긴 부분 수열을 의미했다.

이번 문제에서는 바이토닉 수열이기 때문에 정점으로 올라가 정점에서 내려와야 한다.

그렇다면 정점을 기준으로 삼아 DP를 세울 수 있을 것 같다.

DP[i]는 정점이 i인 가장 긴 바이토닉 수열이다. i를 무조건 포함하여야 하기 때문에 i까지의 가장 긴 증가하는 부분 수열과 i부터의 가장 긴 감소하는 부분 수열의 합으로 이루어져 있는 것을 알 수 있다.

DP_asc를 증가수열, DP_desc를 감소수열이라고 하자.

그렇다면 DP[i] = DP_asc[i] + DP_desc[i] - 1 이 성립한다.

각각에 대해서 따로 구하기만 하면 전체 DP값을 얻을 수 있다.

단, DP_desc는 어떻게 처리하면 될까? 이는 i부터 읽으면서 내림차순으로 갱신해도 되고 뒤에서부터 읽으면서 오름차순으로 갱신해도 된다.

난 후자의 방식으로 코드를 작성했다.

코드

---

import java.util.*;
import java.io.*;

public class Main {
  static int N;
  static int[] arr;
  static int[] dp;
  static int[] dp_asc;
  static int[] dp_desc;
  static int max = Integer.MIN_VALUE;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    N = Integer.parseInt(br.readLine());
    arr = new int[N];
    dp = new int[N];
    dp_asc = new int[N];
    dp_desc = new int[N];

    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }

    ascending();
    descending();

    for (int i = 0; i < N; i++) {
      dp[i] = dp_asc[i] + dp_desc[i] - 1;
      max = Math.max(max, dp[i]);
    }

    System.out.println(max);
  }

  static void ascending() {
    for (int i = 0; i < N; i++) {
      dp_asc[i] = 1;
      for (int j = 0; j < i; j++) {
        if (arr[j] < arr[i] && dp_asc[i] < dp_asc[j] + 1) {
          dp_asc[i] = dp_asc[j] + 1;
        }
      }
    }
  }

  static void descending() {
    for (int i = N - 1; i >= 0; i--) {
      dp_desc[i] = 1;
      for (int j = i + 1; j < N; j++) {
        if (arr[j] < arr[i] && dp_desc[i] < dp_desc[j] + 1) {
          dp_desc[i] = dp_desc[j] + 1;
        }
      }
    }
  }
}

결과

---