[백준/Python] 11054 가장 긴 바이토닉 부분 수열

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

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

가장 긴 증가 부분 수열과 가장 긴 감소 부분 수열을 적용하여, 그 결과를 합하면 해결이 될 것이라 생각했다! 

하지만 백준 반례를 도입해서 고민해봐도 도저히 답이 찾아지지 않아 해답을 찾아보았다. 

 

내가 실수했던 것은,

그저 증가수열과 감소수열의 결과에서 각각의 최댓값을 더하면 된다고 생각한 것이었다.

바이토닉 부분 수열이란, 계속 증가되던 부분 수열의 최댓값에서 -> 다시 감소되기 시작하는 수열을 말하는 것! 

 

이해가 쉽게 문제의 예시를 그림으로 표현해보자면 아래와 같다. 

 

 

만약 처음 생각한 대로 코드를 작성할 경우,

가장 큰 증가수열의 최댓값 인덱스부터 감소되기 시작하는 수열을 구하는 것이 아니라

첫 인덱스부터 가장 긴 감소 수열의 값을 구하게 되어 그저 각각의 값을 더하는 결과로 도출된다는 것을 깨달았다. 

 

따라서, 

LIS수열을 구함과 동시에 입력된 배열을 거꾸로 넣으며 역 LIS 수열을 구한 뒤,

각 인덱스의 합에서 최댓값을 출력하면 된다! 

 

다만 주의할 점은, 결과값에서 -1을 해줘야 한다. 

해당 인덱스가 두번 계산된 결과이기 때문! 

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

dp_increase = [1]*n
dp_decrease = [1]*n

for i in range(n):    
    for j in range(i): 
        if array[j] < array[i] and dp_increase[i] < dp_increase[j]+1:
            dp_increase[i] = dp_increase[j]+1

#실패한 코드 
# for i in range(n):
#     for j in range(i):
#         if array[i]<array[j] and dp_decrease[i]<=dp_decrease[j]:
#             dp_decrease[i] += 1

for i in range(n-1, -1, -1):    
    for j in range(n-1, i, -1): 
        if array[j] < array[i] and dp_decrease[i] < dp_decrease[j]+1:
            dp_decrease[i] = dp_decrease[j]+1


result = [0]*n
for i in range(n):
    result[i] = dp_increase[i] + dp_decrease[i]


print(max(result)-1)

 

응용은 너무 어렵다......

그래도 꾸준히 반복학습해보자!