(백준 알고리즘 문제풀이) 11054번 가장 긴 바이토닉 부분 수열

문제

 

문제 링크

 

문제 접근

• 바이토닉 부분 수열이라는 것은 예를 들어 1 2 3 4 5 4 3 2 1 등과 같이 오름차순으로 정렬되었다가 내림차순으로 정렬이 된 수열 일컷는다.
• 바이토닉 수열은 이전에 구현한 가장 긴 증가하는 부분수열을 이용하는 것이다.
• 가장 긴 증가하는 부분 수열 알고리즘과 기존 수열의 reverse한 후 가장 긴 증가하는 부분 수열 알고리즘 결과 값을 더한 후 + 1을 해주면 된다.

코드

import sys

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

dp = [0] * N

for i in range(N):
    for j in range(i):
        if seq[i] > seq[j]:
            dp[i] = max(dp[i], dp[j] + 1)

seq.reverse()
dp2 = [0] * N
for i in range(N):
    for j in range(i):
        if seq[i] > seq[j]:
            dp2[i] = max(dp2[i], dp2[j] + 1)

dp2.reverse()

result_dp = [0] * N
for i in range(N):
    result_dp[i] = dp[i] + dp2[i] + 1

# print(dp)
# print(dp2)
# print(result_dp)
print(max(result_dp))

느낀점

수열 문제에 익숙해져서 그런지 생각을 하는데 오랜 시간이 걸리지 않았다. 역시 알고리즘은 익숙해져야 한다고 느낀다.