[JAVA] 백준 (골드4) 11054번 가장 긴 바이토닉 부분 수열

링크

https://www.acmicpc.net/problem/11054

---

문제 설명

정답률 50.947%

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {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가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

---

입력 예제

10
1 5 2 1 4 3 4 5 2 1

---

출력 예제

7

---

풀이

가장 긴 증가하는 부분 수열의 카테고리 문제이다. 최장 증가 부분수열(LIS)가 있으면 최장 감소 부분수열(LDS)도 있다. 바이토닉 수열은 오름차순이거나 내림차순이거나 증가하다 감소하는 수열인데 우선 예제의 LIS를 구해보면 다음과 같다.

수열의 각 수에 대해 재귀를 호출하며 이전 수에 대하여 자신보다 작은 수를 메오이제이션 배열에 저장해나간다.

static int LIS(int x) {

    if (lisDp[x] == null) {
        lisDp[x] = 1;
        
        for (int i = x - 1; i >= 0; i--) {
            if (seq[x] > seq[i]) {
                lisDp[x] = Math.max(lisDp[x], LIS(i) + 1);
            }
        }
    }
    return lisDp[x];
}

이제 LDS를 구해보면 다음과 같다.

LIS와 동일하나 이전 수에 대한게 아니라 다음 수부터 마지막 수까지 자신보다 작은 수를 카운트한다.

static int LDS(int x) {

    if (ldsDp[x] == null) {
        ldsDp[x] = 1;
        
        for (int i = x + 1; i < N; i++) {
            if (seq[x] > seq[i]) {
                ldsDp[x] = Math.max(ldsDp[x], LDS(i) + 1);
            }
        }
    }
    return ldsDp[x];
}

바이토닉 수열은 LDS와 LIS의 결괏값을 합치면 된다. 단 자기 자신이 중복으로 카운트되므로 -1을 해준다.

코드

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

//백준
public class Main {

    static Integer[] lisDp;
    static Integer[] ldsDp;
    static int[] seq;
    static int N;

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        lisDp = new Integer[N];
        ldsDp = new Integer[N];
        seq = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        for (int i = 0; i < N; i++) {
            LIS(i);
            LDS(i);
        }
        //dp배열 합침
        for (int i = 0; i < N; i++) {
            lisDp[i] += ldsDp[i];
        }

        int max = Arrays.stream(lisDp)
                .mapToInt(Integer::intValue)
                .max()
                .orElseThrow();

        System.out.println(max - 1);
    }
    //최장 증가 부분수열
    static int LIS(int x) {

        if (lisDp[x] == null) {
            lisDp[x] = 1;

            for (int i = x - 1; i >= 0; i--) {
                if (seq[x] > seq[i]) {
                    lisDp[x] = Math.max(lisDp[x], LIS(i) + 1);
                }
            }
        }

        return lisDp[x];
    }
    //최장 감소 부분수열
    static int LDS(int x) {

        if (ldsDp[x] == null) {
            ldsDp[x] = 1;

            for (int i = x + 1; i < N; i++) {
                if (seq[x] > seq[i]) {
                    ldsDp[x] = Math.max(ldsDp[x], LDS(i) + 1);
                }
            }
        }

        return ldsDp[x];
    }
}