Baekjoon | Q.11054 - 가장 긴 바이토닉 부분 수열

11054번: 가장 긴 바이토닉 부분 수열

바이토닉 수열이란 S(1) < S(2) < S(3) < ··· < S(k-1) < S(k) > S(k+1) > S(k+2) > ··· > S(n-1) > S(n)을 만족하는 수열이다. 주어진 수열의 부분 수열 중에서 가장 긴 바이토닉 수열을 찾는 문제이다.

import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    int[] lis_front = new int[n];
    int[] lis_back = new int[n];

    for (int i = 0; i < n; i++) {
      arr[i] = sc.nextInt();
    }

    sc.close();
    
    for (int i = 0; i < n; i++) {
      int now = arr[i];
      int max_front = 0;

      lis_front[i] = 1;

      for (int j = 0; j < i; j++) {
        if(now > arr[j] && max_front < lis_front[j]) {
          max_front = lis_front[j];
        }
      }

      lis_front[i] = max_front + 1;
    }

    for (int i = n-1; i >= 0; i--) {
      int now = arr[i];
      int max_back = 0;
      lis_back[i] = 1;

      for (int j = n-1; j > i; j--) {
        if(now > arr[j] && max_back < lis_back[j]) {
          max_back = lis_back[j];
        }

        lis_back[i] = max_back + 1;
      }

    }
    
    int max = 0;
    for (int i = 0; i < n; i++) {
      int now = lis_front[i] + lis_back[i] - 1;
      if(now > max) max = now;
    }

    System.out.println(max);

  }
}

 가장 긴 증가하는 부분 수열(LIS)의 응용 문제이다.

Baekjoon | Q.11053 - 가장 긴 증가하는 부분 수열

 주어진 수열의 앞부분부터 LIS를 구하고, 뒤에서부터 거꾸로 LIS를 찾는다. 앞에서부터 뒤로 진행한 lis_front[i]와 뒤에서부터 거꾸로 진행한 lis_back[i]을 더한 값에 -1을 해주면 arr[i]를 중간값으로 가지는 가장 긴 바이토닉 부분수열의 길이가 된다. -1을 해주는 이유는 두 부분 수열에서 arr[i]가 중복으로 나타나기 때문이다.

 

 예시로 주어진 {1, 5, 2, 1, 4, 3, 4, 5, 2, 1 }를 살펴보자.

i	0	1	2	3	4	5	6	7	8	9
lis_front	1	1, 5	1, 2	1	1, 2, 4	1, 2, 3	1, 2, 3, 4	1, 2, 3, 4, 5	1, 2	1
lis_back	1	1, 2, 3, 4, 5	1, 2	1	1, 2, 3, 4	1, 2, 3	1, 2, 4	1, 2, 5	1, 2	1

arr[7]에 위치한 5가 중간 값일 때 가장 긴 바이토닉 부분 수열 {1, 2, 3, 4, 5, 2, 1}을 가진다. 중복값인 5를 빼주자.