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

백준 11054번

최종 제출 코드

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

asc_dp = [1]*n
desc_dp = [1]*n

for i in range(1, n):
  for j in range(i):
    # 부분 수열의 증가하는 최대 길이의 수열 길이 구하기
    if array[i] > array[j]:
      asc_dp[i] = max(asc_dp[j]+1, asc_dp[i])
      
    # 부분 수열의 감소하는 최대 길이의 수열 길이 구하기
    # array를 역순으로 탐색
    if array[n-i-1] > array[n-j-1]:
      desc_dp[n-i-1] = max(desc_dp[n-j-1]+1, desc_dp[n-i-1])

# 최대 길이의 바이토닉 부분 수열의 길이 구하기
max_len = 0
for k in range(n):
  if asc_dp[k] + desc_dp[k] > max_len:
    max_len = asc_dp[k] + desc_dp[k]

print(max_len-1)

.
◼ 가장 긴 부분 수열 구하기 문제와 풀이 유사

• 차이점은 array[i]를 기준으로 두고 ~array[i] 범위에서 증가하는 최대 길이의 부분 수열 길이 구할 뿐만 아니라, array[i]~ 범위에서 감소하는 최대 길이의 부분 수열의 길이도 구해야 한다는 것이다.
• desc_dp를 업데이트 하는 반복문에서는 인덱스값을 이용해 array를 가장 마지막 원소부터 array[i] 원소까지 역순으로 탐색하게 한다.

.
◼ 최대 길이의 바이오닉 수열 구하기

• asc_dp와 desc_dp를 탐색하며 각 배열에 저장된 값의 합이 가장 큰 값을 고른다.
• 이때 asc_dp[k] + desc_dp[k] 값은 array[k]를 중복으로 포함함으로 최종 결과값은 asc_dp[k] + desc_dp[k] - 1이 된다.