99클럽 코테 스터디 32일차 TIL: 부분 수열 DP 심화

오늘의 문제 | 11054. 가장 긴 바이토닉 부분 수열

부분수열 시리즈 중에 가장 어려워보여서 도전하지 않았던 문제이다. 다만 조금 생각해보니, 기존에 가장 긴 증가하는/가장 긴 감소하는 부분 수열을 합친 문제라 생각하니 문제가 편해졌다.

아이디어: 각 지점이 중심이라 생각하자.

n=int(input())
l=[*map(int,input().split())]

# 각 지점이 꼭대기일 때를 기준으로 최댓값이 몇인지를 파악하는 걸 목표로 함.

# 해당 지점까지 가장 긴 증가/감소 부분 수열을 둘 다 구하면 가능할 수도.

dp_increase=[1]*(n)
dp_decrease=[1]*(n)
dp_bitonic=[]

for i in range(n):
    for j in range(i):
        if l[j]<l[i]:
            dp_increase[i]=max(dp_increase[i],dp_increase[j]+1)
l=l[::-1]

for i in range(n):
    for j in range(i):
        if l[j]<l[i]:
            dp_decrease[i]=max(dp_decrease[i],dp_decrease[j]+1)
dp_decrease=dp_decrease[::-1]

for i in range(n):
    dp_bitonic.append(dp_increase[i]+dp_decrease[i]-1)
print(max(dp_bitonic))

오늘의 회고

부분 수열을 하다보니 이제 어느정도 이해가 되었다. 확실히 DP 테이블에 어떤 값을 저장하냐를 기준으로 생각하면 되는 듯하다. 다만 테이블을 조금 많이 썼는데 이게 정해인지는 궁금하다.