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

접근

우선 예제를 보고 문제에서 구하고자 하는 바이토닉 수열은 연속되지 않아도 된다는 점을 알았다. 바이토닉 수열은 계속해서 증가하다가 어느 시점을 기점으로 계속해서 감소하는 수열인데, 그러면 배열 하나로 구하기보다는 증가하는 수열의 길이를 담는 배열과 감소하는 수열의 길이를 담는 배열 2개를 계산해서 그 합을 비교하면 될 것 같다. 감소하는 수열은 결국 증가하는 수열을 반대 방향에서 계산한 것과 동일하므로, 부호만 수정해주면 된다. 즉 11053번의 응용 문제이다.

 

그치만 여기까지 생각해놓고 LIS 알고리즘이 생각 안나는 나는,,, 처음에는 스택 두개로 어떻게 해보려고 삽질하다가 이게 맞나 싶어서 결국 솔루션을 찾아봤다. 해보지는 않았는데 스택 방법도 논리적으로는 문제가 없다고 생각한다.. 아마도? 간략하게만 적어보면 스택 2개를 두고, 하나에는 (현재) 가장 긴 증가하는 수열을 저장 / 나머지 하나는 (앞으로) 가장 길 수도 있는 수열을 저장하는 것이었다. 그래서 만약 {7, 8, 9, 1, 2, 3, 4, 5} 가 있다면 뒤쪽의 5숫자가 가장 길기 때문에, 작은 수가 나온다면 임시 후보로 스택에 저장해두다가 그 길이가 더 길어지면 스위치하는 방식을 생각해봤다. 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int answer = 0;

        int[] arr = new int[n];
        int[] increase = new int[n];
        int[] decrease = new int[n];

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

        // 최장 증가 수열(LIS) 구하기
        for(int i = 0;i < n;i++){
            increase[i] = 1;
            for(int j = 0;j < i;j++){
                if(arr[i] > arr[j])
                    increase[i] = Math.max(increase[i], increase[j] + 1);
            }
        }

        // 최장 감소 수열(LDS) 구하기
        for(int i = n-1;i >= 0;i--){
            decrease[i] = 1;
            for(int j = n-1;j >= i;j--){
                if(arr[i] > arr[j])
                    decrease[i] = Math.max(decrease[i], decrease[j]+1);
            }
        }

        for(int i = 0;i < n;i++)
            answer = Math.max(answer, increase[i] + decrease[i]);

        System.out.println(answer - 1); // 가운데 중복되는 숫자 제외
    }
}