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

구현 방법

조건

1. (1 ≤ N ≤ 1,000, 1 ≤ A[i] ≤ 1,000)
   1. N : 수열의 길이
   2. A[i] : i번째 수열A의 값

구현

• 조건 1에 의해서 시간복잡도 O(N^2)으로 충분히 풀 수 있다고 생각했다.
  • → 따라서 DP 사용!
• 바이토닉 부분 수열이 될 수 있는 경우는 3가지가 있다.
  1. 계속 증가
  2. 계속 감소
  3. 증가하다가 감소
• 바이토닉 부분 수열이 될 수 있는 경우가 3가지를 바탕으로 필요한 정보는 다음과 같다.
  • dpDESC[i] : i번째부터 (N - 1)번째까지 감소하는 수열 중 가장 긴 수열
  • dpASC[i] : 0번째부터 i번째까지 증가하는 수열 중 가장 긴 수열
• 위의 두 정보를 더하고, 중복된 i번째 하나를 빼면 원하는 답이 나온다.
  • dp[i] = dpASC[i] + dpDESC[i] - 1;

코드

import java.util.*;
import java.io.*;

/**
* 백준 11054
* 가장 긴 바이토닉 부분 수열
* 골드4
* <https://www.acmicpc.net/problem/11054>
*/
public class Boj11054 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] ary = new int[N];
        for(int i = 0; i < N; i++)
            ary[i] = Integer.parseInt(st.nextToken());

        int[] dpASC = new int[N];
        int[] dpDESC = new int[N];
        int[] dp = new int[N];

        for(int i = N - 1; i >= 0; i--) {
            dpDESC[i] = 1;

            for(int j = N - 1; j > i; j--) {
                if(ary[i] > ary[j])
                    dpDESC[i] = Math.max(dpDESC[j] + 1, dpDESC[i]);
            }
        }

        for(int i = 0; i < N; i++) {
            dpASC[i] = 1;

            for(int j = 0; j < i; j++) {
                if(ary[i] > ary[j])
                    dpASC[i] = Math.max(dpASC[j] + 1, dpASC[i]);
            }

            dp[i] = dpASC[i] + dpDESC[i] - 1;
        }

        int max = dp[0];
        for(int i = 1; i < N; i++) {
            max = Math.max(max, dp[i]);
        }

        System.out.println(max);
    }
}