BOJ 11054 - 가장 긴 바이토닉 부분 수열

문제

수열 $S$ 가 어떤 수 $S_k$ 를 기준으로 $S_1 < S_2 < \cdots < S_{k-1} < S_k > S_{k+1} > \cdots > 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가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 $A$ 의 크기 $N$ 이 주어지고, 둘째 줄에는 수열 $A$ 를 이루고 있는 $A_i$ 가 주어진다. $(1 \le N \le 1{,}000,\ 1 \le A_i \le 1{,}000)$

출력

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

풀이

바이토닉 수열은 어떤 정점을 기준으로 왼쪽은 증가, 오른쪽은 감소하는 구조다. 그래서 각 위치를 꼭대기로 삼았을 때의 길이를 계산해 보면 된다.

코드에서는 왼쪽에서부터 증가 부분 수열 길이를 dp_r에, 오른쪽에서부터 감소 방향으로 이어지는 길이를 dp_l에 구한다. 그러면 각 위치 i를 꼭대기로 하는 바이토닉 길이는 dp_r[i] + dp_l[i] - 1이 된다.

증가 부분과 감소 부분을 따로 계산한 뒤 합치는 문제라고 보면 된다.

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    private static int[] arr;
    private static int[] dp_r;
    private static int[] dp_l;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        arr = new int[N];
        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
 
        dp_l = new int[N];
        dp_r = new int[N];
 
        for (int i = 0; i < N; i++)
            LIS(i);
 
        for (int i = N - 1; i >= 0; i--)
            LDS(i);
 
        int ans = -1;
        for (int i = 0; i < N; i++)
            ans = Math.max(ans, dp_l[i] + dp_r[i]);
 
        System.out.println(ans - 1);
    }
 
    // 최장 증가 부분수열
    private static void LIS(int N) {
        if (dp_r[N] == 0)
            dp_r[N]++;
 
        for (int i = 0; i < N; i++)
            if (arr[N] > arr[i])
                dp_r[N] = Math.max(dp_r[N], dp_r[i] + 1);
    }
 
    // 최장 감소 부분수열
    private static void LDS(int N) {
        if (dp_l[N] == 0)
            dp_l[N]++;
 
        for (int i = dp_l.length - 1; i >= N ; i--)
            if (arr[N] > arr[i])
                dp_l[N] = Math.max(dp_l[N], dp_l[i] + 1);
    }
 
}

복잡도

시간 복잡도: 각 위치에서 증가/감소 부분 수열을 이중 반복으로 계산하므로 $O(N^2)$ 이다.
공간 복잡도: 양방향 DP 배열을 저장하므로 $O(N)$ 이다.

마무리

바이토닉은 증가와 감소를 한 번에 보지 않고, 각 위치를 꼭대기로 두고 좌우를 따로 계산하면 된다. LIS를 두 방향에서 구해 합치는 관점이 핵심이다.

문제#

입력#

출력#

풀이#

코드#

복잡도#

마무리#

문제

입력

출력

풀이

코드

복잡도

마무리