[BOJ 11045] 가장 긴 바이토닉 부분 수열

문제

• BOJ 11045
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

위 그림 처럼, 가장 긴 바이토닉 부분 수열이 되는 조건은 1)오름차순 2)내림차순 3)오름차순에서 내림차순인 수열, 이 세가지 수열 중 최대 길이인 경우이다.
그런데, 3)번은 어떻게 구해야할 지 고민할 필요가 있다.
오름차순은 구하기 쉽지만, 내림차순의 경우는 오른쪽에서 부터 증가하는 수열과 같은 케이스라는 사실을 알아야 한다.

1. 오름차순인 부분 수열을 구하기 위해 왼쪽에서 증가하는 수열의 길이를 구해 각 인덱스의 배열값 저장한다.
2. 내림차순인 부분 수열을 구하기 위해 오른쪽에서 증가하는 수열의 길이를 구해 각 인덱스의 배열값에 저장한다.

1번과 2번에서 구한 값을 더한 결과 중 가장 큰 최대값으로 바이토닉 수열의 최대 길이를 구할 수 있다.
이때 주의할 점은 현재 인덱스값이 두번 더해지기 때문에 중복을 빼기 위해 길이-1을 해주어야 한다.

코드

import java.util.Scanner;

//가장 긴 바이토닉 부분 수열
public class Main {

    static int n; //삼각형의 크기
    static int[] arr;
    static int[] f;
    static int[] r;
    static int Ans;

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

        arr = new int[n];

        //현재 인덱스값의 증가하는 수열의 길이 저장
        f = new int[n];
        r = new int[n];

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

        //맨앞부터 LIS구하기
        for(int i=0; i<n; i++){
            f[i] = 1; //초기 길이1
            for(int j=0; j<i; j++) { //현재 인덱스 이전에서 현재 원소값보다 더 작은 원소를 찾는다.
                if (arr[j] < arr[i] && f[j] + 1 > f[i]) f[i]++; //선택 시 길이가 증가하면 갱신
            }
        }


        //맨뒤부터 LIS구하기
        for(int i=n-1; i>=0; i--){
            r[i] = 1; //초기 길이1
            for(int j=n-1; j>i; j--){ //현재 인덱스 이전에서 현재 원소값보다 더 작은 원소를 찾는다.
                if(arr[j] < arr[i] && r[j]+1>r[i]) r[i]++; //선택 시 길이가 증가하면 갱신
            }
        }

        //두 LIS의 합의 최대값 구하기
        for(int i=0; i<n; i++) Ans = Math.max(Ans, f[i] + r[i]);

        System.out.println(Ans-1); //가운데값이 겹치므로 하나뺌
    }
}