2026-01-21

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

동적 계획법(DP)을 활용하여
증가 수열과 감소 수열을 결합하는 문제를 학습했다.

1. 문제 핵심 요약

수열에서 하나의 원소를 봉우리(peak) 로 잡았을 때,

• 왼쪽은 증가하는 부분 수열
• 오른쪽은 감소하는 부분 수열

이 되도록 구성할 수 있는 가장 긴 부분 수열의 길이를 구하는 문제이다.

2. 핵심 개념 정리

2-1. 부분 수열 (Subsequence)

• 연속일 필요 없음
• 인덱스의 순서만 유지하면 됨

2-2. LIS (Longest Increasing Subsequence)

i에서 끝나는 최장 증가 부분 수열의 길이

• DP 정의
  inc[i] = i를 마지막으로 사용하는 LIS 길이

• 점화식

  • j < i 이고 A[j] < A[i] 인 경우
  • inc[i] = max(inc[j]) + 1
  • 해당 조건이 없으면 inc[i] = 1

2-3. LDS (Longest Decreasing Subsequence)

i에서 시작하는 최장 감소 부분 수열의 길이

• DP 정의
  dec[i] = i를 시작으로 하는 LDS 길이

• 계산 방법

  • 오른쪽에서 왼쪽으로 DP
  • j > i 이고 A[j] < A[i] 인 경우
  • dec[i] = max(dec[j]) + 1

3. 바이토닉 수열의 핵심 아이디어

어떤 인덱스 i를 봉우리로 선택했을 때, 바이토닉 길이 = inc[i] + dec[i] - 1

• i가 증가/감소 수열에 중복 포함되므로 -1 필요
• 모든 i에 대해 계산 후 최대값이 정답

4. 전체 풀이 흐름

1. LIS DP로 inc[i] 계산 (왼쪽 → 오른쪽)
2. LDS DP로 dec[i] 계산 (오른쪽 → 왼쪽)
3. 모든 i에 대해 inc[i] + dec[i] - 1 최대값 탐색

5. 시간 복잡도

• LIS: O(N^2)
• LDS: O(N^2)
• 전체: O(N^2)

N ≤ 1000 이므로 충분히 통과 가능

6. 실수하기 쉬운 포인트

• 증가/감소 조건은 엄격 비교(<)
• inc + dec 계산 시 -1 누락 주의
• dec[i]는 반드시 i에서 시작하는 감소 수열로 정의해야 함

7. 정리

이 문제는
“바이토닉 수열 = LIS + LDS” 라는 구조를 정확히 이해하면
DP를 두 번 적용하는 전형적인 문제였다.

특히,

• LIS는 끝
• LDS는 시작

이라는 기준을 분명히 잡는 것이 핵심이다.