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

gmlwlswldbs·2021년 9월 21일
0

코딩테스트

목록 보기
32/130
n = int(input())
a = list(map(int, input().split()))


d1 = [1] * n
d2 = [1] * n
for k in range(n):
    for j in range(k):
        if a[j] < a[k] and d1[k] < d1[j] + 1:
            d1[k] = d1[j] + 1
    
for k in range(n-1, -1, -1):
    for j in range(k+1, n):
        if a[j] < a[k] and d2[k] < d2[j] + 1:
            d2[k] = d2[j] + 1
ans = 0
for i in range(n):
    ans = max(ans, d1[i] + d2[i]-1)

print(ans)
  1. 앞에서부터 증가하는 가장 긴 수열 2. 뒤에서부터 증가하는 가장 긴 수열
    두가지 배열을 만들어서 브루트포스로 각 인덱스를 기준으로 두 값의 합이 가장 큰거 구함
    (인덱스까지 증가 + 감소 = 바이토닉)
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    d1 = [1] * n
    d2 = [1] * n
    for k in range(i+1):
        for j in range(k):
            if a[j] < a[k] and d1[k] < d1[j] + 1:
                d1[k] = d1[j] + 1
    
    for k in range(i+1, n):
        for j in range(i+1, k):
            if a[j] > a[k] and d2[k] < d2[j] + 1:
                d2[k] = d2[j] + 1

    ans= max(max(d1) + max(d2), ans)

print(ans)

처음에는 인덱스 기준 앞은 증가하는, 뒤는 감소하는 가장 긴 수열을 인덱스마다 계산해서 3중 for문을 돌리려했어서 시간 초과가 남

0개의 댓글