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

문제 링크

1.

예전에 풀었던 가장 긴 증가하는 부분 수열 (11053)의 응용문제이다.

해당 문제의 풀이법을 잊었었는데, 다시 복습하며 문제를 풀었다. 복습의 중요성을 깨닫는다.

 

 

2.

이번에 알게 된 것인데, 가장 긴 증가하는 부분 수열을 구하는 알고리즘을 부르는 명칭이 존재했다.

이는 LIS 알고리즘으로, Longes Increasing Subsequence 의 줄임말이다.

 

이번 바이토닉 부분 수열을 구할 때에 이 LIS 알고리즘을 잘 적용하여야 한다.

 

 

가장 긴 바이토닉 부분 수열은 증가하다가 감소하는 부분 수열의 길이가 가장 긴 것을 구해야 한다.

 

이를 다시 말하면,

1. 증가하는 부분 수열의 길이 값도 최대로

2. 감소하는 부분 수열의 길이 값도 최대로 하여야 한다.

 

즉, 증가하는 부분 수열의 dp 배열 값과 감소하는 부분 수열의 dp 배열 값을 서로 더하여 최댓값을 찾는다면 1, 2를 모두 충족할 것이다.

 

참고로 dp 배열은 해당 원소까지 가장 긴 증가 or 감소하는 부분 수열의 개수를 나타낸다.

 

 

먼저 증가하는 부분 수열의 길이를 구해보자.

 

다음으로 감소하는 부분 수열의 길이를 구해보자.

이는 뒤에서부터 증가하는 부분 수열의 길이를 구하는 것과 동일하다.

 

이 두 dp배열의 합의 최댓값은 8로,

dpLR에서는 1, 2, 4, 5가 선택되고 dpRL에서는 5, 2, 1가 선택되는데 5가 중복되므로 1을 빼준다.

 

 

3.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] arr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = sc.nextInt();
        }

        // 왼쪽에서 오른쪽으로 LIS 구하기
        int[] dpLR = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dpLR[i] = 1;
            for (int j = 1; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dpLR[i] = Math.max(dpLR[j] + 1, dpLR[i]);
                }
            }
        }

        // 오른쪽에서 왼쪽으로 LIS 구하기
        int[] dpRL = new int[n + 1];
        for (int i = n; i > 0; i--) {
            dpRL[i] = 1;
            for (int j = n; j > i; j--) {
                if (arr[i] > arr[j]) {
                    dpRL[i] = Math.max(dpRL[j] + 1, dpRL[i]);
                }
            }
        }

        // 두 dp 배열의 합의 최대값 찾기
        int max = 0;
        for (int i = 1; i <= n; i++) {
            max = Math.max(max, dpLR[i] + dpRL[i]);
        }

        System.out.println(max - 1); // 해당 원소 중복되므로 -1
        sc.close();
    }
}

 

 

4.

LIS 알고리즘. 기억하자.

 

 

[참고] https://fbtmdwhd33.tistory.com/54

[참고] https://fbtmdwhd33.tistory.com/56