[파이썬(Python)] 백준 11054번 가장 긴 바이토닉 부분 수열

 

 

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

문제 바로 가기

---

📌 문제

수열 $S$가 어떤 수 $S_k$를 기준으로 $S_1 < S_2 < ... S_{k-1} < S_k > S_{k+1} > ... 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 ≤ N ≤ 1,000, 1 ≤ A_i ≤ 1,000)$

출력

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

 

 

 

 

 

 

 

 

 

 

📝 아이디어

 

 

문제 분석

 

이 문제는 주어진 수열 $A$에서 가장 긴 바이토닉 부분 수열의 길이를 구하는 문제입니다. 

 

 

 

바이토닉 수열은 아래의 조건을 만족하는 수열입니다.

 

 

특정 원소 $A[k]$를 기준으로

• 왼쪽은 증가하는 부분 수열을 형성합니다.

$$(A[1] < A[1] < \dots < A[k-1] < A[k])$$

• 오른쪽은 감소하는 부분 수열을 형성합니다.

$$(A[k] > A[k+1] < \dots < A[N])$$

 

 

 

 

부분 수열이란 주어진 수열 $A$에서 특정 원소들을 선택해 순서를 유지하며 만든 새로운 수열을 말합니다. 예를 들어 $A = [1, 5, 2, 1]$일 때 $[1, 5, 2]$는 부분 수열입니다. 여기서 중요한 점은 연속적일 필요는 없으며 원소의 순서만 유지하면 됩니다. 

 

 

 

 

 

 

 

아이디어

 

 

이 문제를 해결하기 위해서는 가장 긴 증가하는 부분 수열(LIS)과 가장 긴 감소하는 부분 수열(LDS)의 개념을 활용해야 합니다. 해결 과정은 크게 세 단계로 나눌 수 있습니다. 

 

 

1. 왼쪽에서 증가하는 부분 수열의 길이(LIS)

이 단계는 백준 11053번 가장 긴 증가하는 부분 수열 문제와 동일한 접근법으로 해결할 수 있습니다.

 

 

$\text{LIS}[i]$를 $A[i]$를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이라고 정의합니다. 

 

$$\text{LIS}[i] = \max (\text{LIS}[i], \text{LIS[j] + 1}) \quad (\text{for all} \; j < i \; \text{and} \; A[j] < A[i])$$

 

각 원소는 자기 자신만으로도 길이 1의 증가하는 부분 수열을 형성하므로 $\text{LIS}[i] = 1$로 초기화합니다. 

 

 

 

 

 

2. 오른쪽에서 감소하는 부분 수열의 길이(LDS)

이 단계는 백준 11722번 가장 긴 감소하는 부분 수열 문제와 동일한 접근법으로 해결할 수 있습니다.

 

 

$\text{LDS}[i]$를 $A[i]$를 마지막으로 하는 가장 긴 감소하는 부분 수열의 길이라고 정의합니다.



$$\text{LDS}[i] = \max (\text{LDS}[i], \text{LDS[j] + 1}) \quad (\text{for all} \; j > i \; \text{and} \; A[j] < A[i])$$

 

각 원소는 자기 자신만으로도 길이 1의 감소하는 부분 수열을 형성하므로 $\text{LDS}[i] = 1$로 초기화합니다. 

 

 

 

 

 

3. 바이토닉 수열의 길이 계산

 

각 원소 $A[i]$를 기준으로 바이토닉 수열의 길이를 계산합니다. $A[i]$를 포함하는 바이토닉 수열의 길이는 다음과 같습니다.

 

$$\text{length} = LIS[i] + LDS[i] - 1$$

 

여기서 -1은 $A[i]$가 중복되므로 이를 제거하기 위해 빼줍니다.

 

 

마지막으로 모든 $i$에 대해 계산된 바이토닉 수열의 길이 중 최댓값을 반환합니다. 

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

n = int(input())
a = list(map(int, input().split()))


lis = [1] * n
for i in range(n):
    for j in range(i):
        if a[j] < a[i]:
            lis[i] = max(lis[i], lis[j] + 1)

lds = [1] * n
for i in range(n - 1, -1, -1):
    for j in range(n - 1, i, -1):
        if a[j] < a[i]:
            lds[i] = max(lds[i], lds[j] + 1)

max_len = 0
for i in range(n):
    max_len = max(max_len, lis[i] + lds[i] - 1)

print(max_len)