[다이나믹 프로그래밍] 11054번 - 가장 긴 바이토닉 부분 수열

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

(한줄평) LIS 응용 문제로 LIS(최장증가부분수열)알고리즘을 안다면 쉽게 풀 수 있었던 문제!

풀이 시간: 15분 이내

 

1) 문제 해결 아이디어

n이 1이상 1000이하인 길이가 n인 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 구하는 문제다. 수열 S가 어떤 수 Sk를 기준으로 (S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN)을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

 

Sk를 기준으로 왼쪽은 가장 긴 부분 증가 수열, 오른쪽은 가장 긴 부분 감소 수열을 구하면 풀 수 있는 문제다. 

가장 긴 부분 감소 수열을 구하기 위해서 입력받은 수열을 reverse해야한다는 것을 잊지말자!

 

<점화식>

2) 소스코드

n = int(input())  # 수열 크기(1이상 1000이하)
graph1 = list(map(int, input().split()))  # 수열 
graph2 = list(reversed(graph1))  # 역순으로 뒤집은 수열
d1 = [1] * n  # 가장 긴 증가하는 부분 수열
d2 = [1] * n  # 가장 긴 감소하는 부분 수열

# 최장 증가 부분 수열 & 최장 감소 부분 수열의 길이 구하기
for i in range(1, n):
  for j in range(i):
    if graph1[j] < graph1[i]:
      d1[i] = max(d1[i], d1[j] + 1)
    if graph2[j] < graph2[i]:
      d2[i] = max(d2[i], d2[j] + 1)
# 최장 증가 부분 수열 & 최장 감소 부분 수열의 길이 합의 최댓값
res = 0
for i in range(n):
  res = max(res, d1[i] + d2[n - 1 - i] - 1)
print(res)