[파이썬/python] 백준 11054번 : 가장 긴 바이토닉 부분 수열 (🥇4)

 

n = int(input())
num = list(map(int,input().split()))
dp1 = [1] * n
dp2 = [0] * n
for i in range(n):
    for j in range(i):
        if num[i] > num[j]:
            dp1[i] = max(dp1[i], dp1[j] + 1)

num.reverse()
for i in range(n):
    for j in range(i):
        if num[i] > num[j]:
            dp2[i] = max(dp2[i], dp2[j] + 1)
dp2.reverse()
for i in range(n):
    dp1[i] += dp2[i]

print(max(dp1))

답은 나오지만 지저분하게 푼 것 같아서 다시 한번 풀어봤다..

 

 

n = int(input())
num = list(map(int,input().split()))
dp1 = [1] * n
dp2 = [0] * n
for i in range(n):
    for j in range(i):
        if num[i] > num[j]:
            dp1[i] = max(dp1[i], dp1[j] + 1)
            
        if num[-(i+1)] > num[-(j+1)]:
            dp2[-(i+1)] = max(dp2[-(i+1)], dp2[-(j+1)] + 1)

for i in range(n):
    dp1[i] += dp2[i]    

print(max(dp1))

n = int(input())
num = list(map(int,input().split()))
dp1 = [1] * n
dp2 = [0] * n
for i in range(n):
    for j in range(i):
        if num[i] > num[j]:
            dp1[i] = max(dp1[i], dp1[j] + 1)

for ii in range(1,n+1):
    for jj in range(1,ii):    
        if num[-ii] > num[-jj]:
            dp2[-ii] = max(dp2[-ii], dp2[-jj] + 1)
    dp1[-ii] += dp2[-ii]    

print(max(dp1))

여러 방법으로 풀어보았는데 제일 위에 풀이가 가장 빠른 시간으로 통과한다.

 

 

n = int(input())
num = list(map(int,input().split()))
num_rvs = num[::-1]
dp1 = [1] * n
dp2 = [0] * n
for i in range(n):
    for j in range(i):
        if num[i] > num[j]:
            dp1[i] = max(dp1[i], dp1[j] + 1)
            
        if num_rvs[i] > num_rvs[j]:
            dp2[i] = max(dp2[i], dp2[j] + 1)

for i in range(n):
    dp1[i] += dp2[-(i+1)]    

print(max(dp1))

다시 코드를 한번 정리하였는데, 배열을 거꾸로 한 것을 복제하여 푸는 것이 깔끔한 풀이법같다.