[알고리즘/DP] 11054번 : 가장 긴 바이토닉 부분 수열 - python

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

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

 

---

• 문제
• 소요시간: 18분 12초

---

• 설계하기(접근방법) 

1. 입력받기

배열을 입력받는다

 

2. 구현하기

이 문제의 핵심 포인트는

가장 긴 산을 만드는 것이다

 

산이라고 하면

        4

      3   

   2          2  

1                 1 

와 같은 형태일 것이다

 

가장 긴 증가하는 부분 수열은 쉽게 구할 수 있다

dp를 선언하여 현재 자신의 값보다 작은 값 중

dp의 길이가 최대값이었던 dp에 +1을 해주면 된다

 

같은 방식으로

가장 긴 감소하는 부분 수열도 쉽게 구할 수 있다 -> dp 2

 

그러면 이 두 개의 정보로 어떻게 가장 긴 바이토닉 부분수열을 만들 수 있을까?

 

최대값이 가장 긴 부분수열을 보장하지 않으므로 우리는 그 중간지점 어딘가를 끊어야 한다

 

dp1과 dp2를 같이 조합하면

특정한 산을 만들 수 있다

 

즉 증가하는 부분 수열 중에서 한 곳을 꼭대기로 잡는다면

감소하는 부분 수열에서 내리막길의 정보를 찾을 수 있다.

 

dp 1 = [1, 2, 2, 1, 3, 3, 4, 5, 2, 1]

dp 2 = [1, 5, 2, 1, 4, 3, 3, 3, 2, 1]

 

즉 인덱스 1번 위치를 탐색하면

1 5 4 3 2 1 인 것을 찾아낼 수 있다

 

꼭대기는 2번 포함되니 둘 값을 더하고 1을 빼면 된다

 

 

 

3. 출력하기

 

즉 dp1과 dp2의 합중에서 가장 큰값에 1을 빼주면 된다

 

---

• 코드(출력)

n  = int(input())

n_list = list(map(int, input().split()))

dp = [1 for _ in range(n)]
dp_2 = [1 for _ in range(n)]
for i in range(n):
    large = 0
    for j in range(i):
        # 기준 수보다 리스트 내의 숫자가 작다면
        if n_list[i] > n_list[j]:
            large = max(large, dp[j])
        dp[i] = large + 1

for i in range(n-1, -1, -1):
    large = 0
    for j in range(n-1, i, -1):
        if n_list[i] > n_list[j]:
            large = max(large, dp_2[j])
        dp_2[i] = large + 1

result = 0
for i in range(n):
    result = max(result, dp[i] + dp_2[i])
    

print(result - 1)

---

• 얻어갈 부분

1. 부분 수열의 정의에 대해서 확실히 하고 갈 수 있었다.