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

cheeeese·2022년 10월 6일
0

코딩테스트 연습

목록 보기
145/151
post-thumbnail

📖 문제

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

💻 내 코드

import sys

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

dp = [1]*n
dec = [1]*n

# 가장 긴 증가하는 부분 수열의 길이 찾기 
for i in range(n-1):
    for j in range(i+1, n):
        if nums[i]<nums[j]:
            dp[j]=max(dp[i]+1, dp[j])


# 뒤에서부터 가장 긴 증가하는 부분 수열의 길이 찾기
for i in range(n-1, 0, -1):
    for j in range(i-1,-1, -1):
        if nums[i]<nums[j]:
            dec[j]=max(dec[j], dec[i]+1)
res = [0]*n
for i in range(n): # 둘의 결과를 더함
    res[i]=dp[i]+dec[i]
print(max(res)-1)

💡 풀이

  • 가장 긴 증가하는 부분 수열의 길이를 두 번 수행해주면 된다
  • 먼저 앞에서부터 구해줌
  • 바이토닉 수열은 중간에 한 수를 기점으로 작아지기 때문에 뒤에서부터 증가하는 부분도 찾아준다
  • 그 둘을 더해주면 증가하는 부분+감소하는 부분을 찾을 수 있게 되고 가장 큰 수가 가장 긴 바이토닉 부분 수열의 길이가 된다

0개의 댓글