[PS] BOJ 11054 / 가장 긴 가장 긴 바이토닉 부분 수열
![[PS] BOJ 11054 / 가장 긴 가장 긴 바이토닉 부분 수열](/content/images/size/w2000/2025/07/-----8.png)
문제 링크: https://www.acmicpc.net/problem/11054
Thumbnail: Photo by Robert Haverly (Unsplash)
LIS? LDS? 이번엔 바이토닉 부분 수열입니다.
풀이
바이토닉 부분 수열?
수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 합니다. 예를 들면, 다음의 경우 모두 바이토닉 수열입니다.
가장 긴 증가하는 수열(LIS), 가장 긴 감소하는 수열(LDS)의 형태도 모두 바이토닉 수열로 볼 수 있습니다.
- 10, 20, 30, 20, 10
- 10, 25, 30, 15, 10
- 10, 20, 30, 40
- 50, 25, 20, 10
반대로, 다음의 경우는 바이토닉 수열이 아닙니다.
- 1, 2, 3, 2, 1, 2, 3, 2, 1
- 10, 20, 30, 40, 20, 30, 40
바이토닉 수열 구성하기
바이토닉 수열은 결국 \(k\)번째 항을 기준으로 앞쪽은 증가하는 수열, 뒷쪽은 감소하는 수열입니다.
즉, 가장 긴 바이토닉 수열을 찾는 과정은 (\(k\)번째 항까지 증가하는 수열 + \(k\)번째 항 이후로 감소하는 수열)의 최대 길이를 구하는 과정이며, 결국 LIS 문제로 풀 수 있습니다.
이제 가장 긴 증가하는 수열과 가장 긴 감소하는 수열을 각각 구해야 합니다.
가장 긴 증가하는 부분 수열 구하기
가장 긴 증가하는 부분 수열을 DP로 구하는 방법은 이전 글에서 정리한 내용을 참고해 주세요 😉
위 글과 동일하게, DP를 사용해 수열의 앞에서부터 가장 긴 증가하는 수열을 구합니다.
increasing = [1] * N
# 증가하는 수열(LIS)은 좌측에서 시작하므로 정방향으로 탐색한다.
for i in range(N):
for j in range(i + 1, N):
if A[j] > A[i]:
increasing[j] = max(increasing[j], increasing[i] + 1)가장 긴 증가하는 부분 수열 구하기
가장 긴 감소하는 부분 수열 구하기
이제 가장 긴 감소하는 부분 수열도 구해야 합니다. 하지만, \(k\)번째 항 이후로 감소하는 수열의 경우 반대로 생각해보면 전체 수열의 끝에서부터 \(k\)번째 항까지 증가하는 부분 수열로 생각할 수도 있습니다.
따라서, 수열의 끝에서부터 역방향으로 가장 긴 증가하는 부분 수열을 구하면 됩니다.
decreasing = [1] * N
# 감소하는 수열(LDS)은 우측에서 시작하므로 역방향으로 탐색한다.
for i in range(N - 1, -1, -1):
for j in range(i - 1, -1, -1):
if A[j] > A[i]: # LDS를 역방향으로 탐색하므로, 점점 커지는 방향으로 수를 찾게 된다.
decreasing[j] = max(decreasing[j], decreasing[i] + 1)가장 긴 감소하는 부분 수열 구하기
가장 긴 바이토닉 부분 수열 구하기
이제, 앞서 구한 increasing과 decreasing 배열을 활용해 가장 긴 바이토닉 부분 수열을 구해야 합니다. 이는 바이토닉 부분 수열의 \(k\)번 원소의 위치를 결정하는 문제로 판단할 수 있습니다.
따라서, 수열의 시작부터 끝까지 반복하며 각 위치를 바이토닉 부분 수열의 \(k\)번 원소가 되도록 하는 경우의 부분 수열의 최대 길이를 계산하고, 그 중 최댓값을 구합니다.
# 임의의 중점을 잡고 양방향에서 LIS + LDS를 했을 때 그 길이가 최대가 되는 것을 찾는다.
# LIS와 LDS도 바이토닉 수열의 일종이다.
max_length = 1
for i in range(N):
max_length = max(max_length, increasing[i] + decreasing[i] - 1) # increasing[i]와 decreasing[i] 모두 i를 포함하므로 1 뺀다.
print(max_length)가장 긴 바이토닉 수열 찾기
전체 코드
input = open(0).readline
N = int(input())
A = list(map(int, input().split()))
increasing = [1] * N
decreasing = [1] * N
# 증가하는 수열(LIS)은 좌측에서 시작하므로 정방향으로 탐색한다.
for i in range(N):
for j in range(i + 1, N):
if A[j] > A[i]:
increasing[j] = max(increasing[j], increasing[i] + 1)
# 감소하는 수열(LDS)은 우측에서 시작하므로 역방향으로 탐색한다.
for i in range(N - 1, -1, -1):
for j in range(i - 1, -1, -1):
if A[j] > A[i]: # LDS를 역방향으로 탐색하므로, 점점 커지는 방향으로 수를 찾게 된다.
decreasing[j] = max(decreasing[j], decreasing[i] + 1)
# 임의의 중점을 잡고 양방향에서 LIS + LDS를 했을 때 그 길이가 최대가 되는 것을 찾는다.
# LIS와 LDS도 바이토닉 수열의 일종이다.
max_length = 1
for i in range(N):
max_length = max(max_length, increasing[i] + decreasing[i] - 1) # increasing[i]와 decreasing[i] 모두 i를 포함하므로 1 뺀다.
print(max_length)solution.py