[백준]바이토닉 부분 수열

1. 문제

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

2. 접근

먼저 해당 문제는 가장 긴 증가하는 부분수열 문제를 풀줄 알아야 접근이 가능하다. 왜냐하면 가장 긴 증가하는 부분수열 문제와 가장 긴 감소하는 부분수열 문제를 합친 게 해당 문제이기 때문이다.

가장 긴 증가하는 부분 수열

• 먼저 해당 문제는 DP 방식으로 풀 수 있다. {1 3 2 4 5}와 같은 배열이 있을 때, for문으로 돌면서 해당 인덱스보다 작은 인덱스를 이중 for문으로 돈다. 그러면 값은 작은데 길이는 가장 길었던 이전 값을 구해 +1을 해주면 된다. 말로 하면 어려우니 예시를 보자

인덱스       0 1 2 3 4
주어진 배열값 1 3 2 4 5
수열 길이    1
-> 인덱스가 0일 때는 이전에 값이 없으니 수열 길이가 1이다

인덱스       0 1 2 3 4
주어진 배열값 1 3 2 4 5
수열 길이    1 2
-> 인덱스가 1, 배열값이 3인 경우 인덱스 0~0을 보자
-> 3보다 작은 배열 값 1만이 존재하고 그 때 수열길이가 1이므로 2(1+1)이 배열값 3의 최대 수열길이다.

인덱스       0 1 2 3 4
주어진 배열값 1 3 2 4 5
수열 길이    1 2 2
-> 인덱스가 2, 배열값이 2인 경우 인덱스 0~1(2-1)을 보자
-> 2보다 작은 배열 값은 1만이 존재하고 그 때 수열길이가 1이므로 2(1+1)이 배열값 2의 최대 수열길이다.

인덱스       0 1 2 3 4
주어진 배열값 1 3 2 4 5
수열 길이    1 2 2 3
-> 인덱스가 3, 배열값이 4인 경우 인덱스 0~2(3-1)을 보자
-> 4보다 작은 배열 값은 1, 3, 2가 존재하고 그 때 수열길이 최대는 2이므로 3(2+1)이 배열값 4의 최대 수열길이다.

인덱스       0 1 2 3 4
주어진 배열값 1 3 2 4 5
수열 길이    1 2 2 3 4
-> 인덱스가 4, 배열값이 5인 경우 인덱스 0~3(4-1)을 보자
-> 5보다 작은 배열 값은 1, 3, 2, 4가 존재하고 그 때 수열길이 최대는 3이므로 4(3+1)이 배열값 5의 최대 수열길이다.

• 위와 같은 방법으로 풀면 시간복잡도는 O(N^2)이지만, 직관적인 방법이기에 이해하기 편하다.
  • 사실 해당 방법에 이분탐색을 적용해 O(NlogN)으로 구할 수 있다. 하지만 그 방법은 수열길이 배열을 구할 수가 없기에 여기서는 사용하지 않았다.
• 이 방법을 사용해서 가장 긴 증가하는 부분수열을 구할 수 있고, 배열을 뒤집으면 가장 긴 감소하는 부분 수열 역시 구할 수 있다.
• 2개의 수열길이가 담긴 배열끼리 더한 후, 최대값-1을 구하면 답이 나온다
  • -1을 하는 이유는 해당 인덱스는 중복되어 2번 들어갔기 때문이다.

3. 코드

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

# 가장 긴 증가하는 부분 수열
up = []
for i in range(n):
  num = arr[i]
  up_max = 0
  for j in range(i):
    if arr[j] < num:
      up_max = max(up_max, up[j])
  up.append(up_max+1)
# 가장 긴 감소하는 부분 수열
down = []
for i in range(n-1,-1,-1):
  num = arr[i]
  down_max = 0
  for j in range(i+1,n):
    if arr[j] < num:
      down_max = max(down_max, down[n-1-j])
  down.append(down_max+1)
print(max([a+b for a,b in zip(up, down[::-1])])-1)