[BOJ/JAVA] P11054 가장 긴 바이토닉 부분 수열

아연·2023년 8월 30일

Algorithm

목록 보기

10/12

문제 설명

수열 S가 어떤 수 S(k)를 기준으로 S(1) < S(2) < ... S(k-1) < S(k) > S(k+1) > ... S(N-1) > S(N)을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

INPUT & OUTPUT

INPUT

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

예제 입력 1

10
1 5 2 1 4 3 4 5 2 1

OUTPUT

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제 출력 1

STRATEGY

💡 바이토닉 수열이란?

어떤 수를 기준으로 증가하다 작아지는 수열

가장 긴 길이의 수열을 구하라고?
그럼 최장 증가 수열, 최장 감소 수열로 구해야겠다 !
dp에는 길이를 담자.
우선 바이토닉 수열의 S(k)를 정하자. S(k)는 A[0]부터 A[A.length - 1]까지 순서대로 해보기로~
S(k)를 기준으로, 왼쪽으로 갈수록(leftDp) & 오른쪽으로 갈수록(rightDp) 더 작아지는지 확인
3 - 1. 작아진다면 재귀로 계속 찾기
구한 두 배열 합치기
→ 해당 index를 기준으로, 왼쪽부터 오름차순 길이 & 오른쪽부터 오름차순 길이가 합해진다!!
근데 여기는 원소 1개 중복이니까 1씩 빼주기
cf) 여기서 중복 원소는 기준 원소: S(k) !
5 - 1. 여기서 가장 큰 원소가 최장 바이토닉 수열의 길이.
5 - 2. 그럼 1씩 빼주지 않고, 가장 큰 원소 구한 다음 -1 해줘도 될 것.

최장 증가 수열(LIS: Longest Increasing Sequence)
최장 감소 수열 (LDS: Longest Decreasing Sequence)

SOLUTION

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

public class Main {

    private static int[] arr;
    private static Integer[] leftDp;
    private static Integer[] rightDp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];

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

        leftDp = new Integer[N];
        rightDp = new Integer[N];

        for (int i = 0; i < N; i++) {
            lis(i);
            lds(i);
        }

        int max = -1;
        for (int i = 0; i < N; i++) {
            max = Math.max(leftDp[i] + rightDp[i], max);
        }
        System.out.println(max - 1);
    }

    private static int lis(int N) {
        if (leftDp[N] == null) {
            leftDp[N] = 1;
            for (int i = N - 1; i >= 0; i--) {
                if (arr[i] < arr[N]) {
                    leftDp[N] = Math.max(leftDp[N], lis(i) + 1);
                }
            }
        }
        return leftDp[N];
    }

    private static int lds(int N) {
        if (rightDp[N] == null) {
            rightDp[N] = 1;
            for (int i = N + 1; i < rightDp.length; i++) {
                if (arr[i] < arr[N]) {
                    rightDp[N] = Math.max(rightDp[N], lds(i) + 1);
                }
            }
        }
        return rightDp[N];
    }
}

REMIND

private static int lis(int N) {
    if (leftDp[N] == null) {
        leftDp[N] = 1;
        for (int i = N - 1; i >= 0; i--) {
            if (arr[i] < arr[N]) {
                leftDp[N] = Math.max(leftDp[N], lis(i) + 1);
            }
        }
    }
    return leftDp[N];
}