99클럽 코테 스터디 32일차 TIL

백준 - 11054번

바이토닉 수열은 LIS, LDS 그리고 LIS + LDS 를 모두 포함한다.

예제 입력의 바이토닉 수열은 1, 2, 3, 4, 5, 2, 1 이며 총 7개로 구성된다.

 

구현 1 - 실패

먼저 LIS의 길이 값이 담긴 배열에서 가장 큰 값을 가진 요소를 찾고,

해당 요소의 인덱스를 기준으로 LDS 길이 값을 구하는 것을 생각했다.

 

LIS : 1, 2, 3, 4, 5

LDS : 5, 2, 1

 

각 부분 수열의 모든 길이를 구하는 것보다, LIS의 최대 길이를 가진 요소를 기준으로 구하는 것이 더 빠르다고 생각했다.
하지만 특정 인덱스를 고정하게 되면, 다른 경우의 수를 놓칠 수 있다.

import java.io.*;
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[] arr = new int[N];
        int[] lis = new int[N];
        int[] lds = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            lis[i] = 1;
            lds[i] = 1;
        }
        br.close();

        // LIS
        int lisCount = 0;
        int ldsStartIdx = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    lis[i] = Math.max(lis[i], lis[j] + 1);
                }
            }
            int beforeCount = lisCount;
            lisCount = Math.max(lisCount, lis[i]);
            if (lisCount != beforeCount) {
                ldsStartIdx = i;
            }
        }

        // LDS
        int ldsCount = 0;
        for (int i = N - 1; i >= ldsStartIdx; i--) {
            for (int j = N - 1; j >= i; j--) {
                if (arr[j] < arr[i]) {
                    lds[i] = Math.max(lds[i], lds[j] + 1);
                }
            }
            ldsCount = Math.max(ldsCount, lds[i]);
        }
        
        // 중복되는 요소(5)가 있기 때문에 -1
        System.out.println(lisCount + ldsCount - 1);
    }
}

 

구현 2

LIS 와 LDS 의 길이 배열을 각각 구하고

두 배열의 같은 인덱스를 가지는 값끼리 더하여 최대 길이를 찾는다.

이때, 하나의 배열을 다른 방식으로 2번 탐색했기 때문에 요소들이 중복되어 있다.

그러므로 최대 길이에서 -1 을 해줘야 한다.

import java.io.*;
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[] arr = new int[N];
        int[] lis = new int[N];
        int[] lds = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            lis[i] = 1;
            lds[i] = 1;
        }
        br.close();

        // LIS
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    lis[i] = Math.max(lis[i], lis[j] + 1);
                }
            }
        }

        // LDS
        for (int i = N - 1; i >= 0; i--) {
            for (int j = N - 1; j >= i; j--) {
                if (arr[j] < arr[i]) {
                    lds[i] = Math.max(lds[i], lds[j] + 1);
                }
            }
        }

        int result = 0;
        for (int i = 0; i < N; i++) {
            result = Math.max(result, lis[i] + lds[i]);
        }

        System.out.println(result - 1);
    }
}

---

백준 11054번 - 가장 긴 바이토닉 부분 수열

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