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

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

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

파이썬 코드

import sys

N = int(sys.stdin.readline())

numbers = list(map(int, sys.stdin.readline().split()))

dp = [0 for _ in range(N)]
dp_inverse = [0 for _ in range(N)]

for i in range(N):
  for v in range(i):
    if numbers[i] > numbers[v]:
      dp[i] = max(dp[i], dp[v])
  dp[i]+=1
    
for i in range(N):
  for v in range(i):
    if numbers[N-1-i] > numbers[N-1-v]:
      dp_inverse[N-1-i] = max(dp_inverse[N-1-i], dp_inverse[N-1-v])
  dp_inverse[N-1-i]+=1

result = 0

for i in range(N):
  result = max(result, dp[i] + dp_inverse[i])

print(result - 1)

풀이법

부분수열 문제에서 다이나믹프로그래밍을 사용하는 것이 아직 익숙하지 않다.

고민했었던 풀이방법을 소개해보자면

• 각 넘버 리스트에서 바이토닉 수열에서 가장 큰 값이 될 수 있는 값을 지정하고 전부 다 구해본다음 마지막에 가장 큰값을 추출하는 것
• 바이토닉 수열에서 최대값이 되는 한 값을 가지고 넘버 리스트의 반복문을 돌면서 만약에 최대값이 되는 부분인 코어가 바뀌면 결과가 바뀌는지 확인하고 업데이트 하는 방식

이런 두개의 방법을 처음에는 많이 고민하고 구현해보았지만

넘버 리스트를 차례대로 돌면서 어떤 값이 나올때마다 규칙적으로 바뀌기 보다는 전체를 다 갈아 엎어야 하는 경우의 수도 존재했다.

그렇다면 하나하나 전부 다시 계산해보아야 하기 때문에 이렇게 구현하게 된다면 조건문도 많아질 뿐더러 시간복잡도도 증가하게된다.

따라서 위의 코드와 같이 구현하기로 방법을 변경했다.

1. 정방향으로 오름차순을 만족하는 최대 개수를 dp에 저장
2. 역방향으로 오름차순을 만족하는 최대 개수를 dp_inverse에 저장
3. dp 와 dp_inverse를 인덱스 순으로 더했을 때 최대값을 구함
4. 바이토닉 수열에서 최대값인 코어값은 dp와 dp_inverse가 겹치게 카운팅을 했으므로 result에서 -1을 해줌