백준 11054 "가장 긴 바이토닉 부분 수열" (JAVA)

🔍 문제링크

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

---

📌 문제 요약

• 바이토닉 수열: 증가했다가 감소하는 형태의 수열
• 수열에서 가장 긴 바이토닉 부분 수열의 길이를 구하는 문제.
• 증가하는 부분 수열(LIS)과 감소하는 부분 수열(LDS)을 결합하여 해결

---

🛠 풀이 및 알고리즘

1. dp1[i]: nums[i]를 마지막 원소로 하는 가장 긴 증가 부분 수열 (LIS).
   • dp1[i] = max(dp1[i], dp1[j] + 1) (nums[i] > nums[j])
2. dp2[i]: nums[i]를 첫 원소로 하는 가장 긴 감소 부분 수열 (LDS).
   • dp2[i] = max(dp2[i], dp2[j] + 1) (nums[i] > nums[j])
3. 바이토닉 부분 수열의 길이 계산
   • dp1[i] + dp2[i] - 1 (중앙값 nums[i]가 중복되므로 -1

---

💡 코드

public class Baekjoon_11054 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] nums = new int[n];
        int[] dp1 = new int[n]; // LIS
        int[] dp2 = new int[n]; // LDS

        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        // 1. LIS (왼쪽에서 오른쪽)
        dp1[0] = 1;
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    dp1[i] = Math.max(dp1[i], dp1[j] + 1);
                }
            }
        }

        // 1. LDS (오른쪽에서 왼쪽)
        dp2[n - 1] = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] > nums[j]) {
                    dp2[i] = Math.max(dp2[i], dp2[j] + 1);
                }
            }
        }

        // 3. 가장 긴 바이토닉 부분 수열 길이 계산
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int cnt = dp1[i] + dp2[i];
            ans = Math.max(ans, cnt);
        }
        System.out.println(ans - 1); // 중앙값은 겹치므로 -1
    }
}

---

🏆 시간 복잡도 분석

• LIS (O(N²)) + LDS (O(N²) = O(N²)
• N ≤ 1000이므로 최악의 경우 O(1,000,000)