[백준 11054] 가장 긴 바이토닉 부분 수열 - python (solved.ac - 골드 3)

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

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

풀이

문제를 보았을때 알수있는 힌트

 

문제를 이해하면 좀 쉽게 풀리는 문제인데. dp 문제로 길게 증가하는 dp1와 감소하는 dp2두개를 만들어서 그 둘을 합치고 겹치는 구간 1을 빼면 쉽게 풀리는 문제이다.

dp2를 구하기 위해서 list를 역순으로 뒤집어서 쉽게 계산했다. 나온 결과를 다시 reverse 시키고 dp1과 더하면 끝이 난다.

 

import sys

input= sys.stdin.readline

n= int(input())

n_list=list(map(int,input().split()))

# print(max_list)
result=[]
dp1=[1 for _ in range(n)]
dp2=[1 for _ in range(n)]

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

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

for i in range(n):
    result.append(dp1[i]+dp2[i])

print(max(result)-1)

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon11054.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리