백준 알고리즘 - 가장 긴 바이토닉 부분 수열 (11054) [Python]

 문제

 

www.acmicpc.net/problem/11054

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

 

 

 

 

 

 문제 상황

 

- 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

 

- 주어진 수열에서 길이가 최대가 되는 바이토닉 부분 수열을 찾는다.

 

 

 

 

 

 해결 전략

 

- LIS가 양쪽으로 있는 문제이다. 

 

- 처음에는 기분 인덱스 i를 옮겨가며 양쪽에서 LIS를 계산해 답을 도출하려고 하였다. 하지만 이렇게 되면 i를 움직이는 for문이 하나 더 생겨 결국 O(N^3)이 되었다. N값이 아주 크지 않더라도 되도록이면 반복문을 줄이는 방향으로 코드를 작성해야한다.

 

 

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
N = int(input())
N_list = list(map(int, input().split()))
rev_list = N_list[::-1]
cache = [1] * N
cache2 = [1] * N
for i in range(1, N):
    for j in range(i):
        if N_list[i] > N_list[j]:
            cache[i] = max(cache[i], cache[j]+1)
        if rev_list[i] > rev_list[j]:
            cache2[i] = max(cache2[i], cache2[j]+1)
cache2 = cache2[::-1]
for i in range(N):
    cache[i] += cache2[i]-1
print(max(cache))
 
 
# 시간초과 코드
from sys import stdin
input = stdin.readline
N = int(input())
N_list = list(map(int, input().split()))
def lis(lst, cache):
    for i in range(1, len(lst)):
        for j in range(i):
            if lst[i] > lst[j]:
                cache[i] = max(cache[i], cache[j]+1)
    return cache[len(lst)-1]
dp = [0] * (N)
for i in range(N): # 바이토닉의 중심 정하기
    cache = [1]*(i+1)
    cache2 = [1]*(N-i)
    forward = lis(N_list[:i+1], cache)
    backward = lis(N_list[i:][::-1], cache2)
    dp[i] = forward + backward - 1
print(max(dp))

 

 

 

 

 

 해설

 

- 아래에서 3중 for문의 속도 이슈가 발생하므로 위의 코드는 3중 for문을 2중, 단일 for문으로 분리하여 연산했다. 왼쪽부터 오른쪽으로 LIS를 풀고, 오른쪽에서 왼쪽으로 LIS를 푸는데 이를 이중 for문 한번으로 처리하기 위해 reverse해서 연산하였다.

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 처음에는 문제를 잘못 이해해서 부분 수열이 아니라 연속된 바이토닉을 찾았다. 문제가 너무 쉬워 이상했다.