11054. 가장 긴 바이토닉 부분 수열 (Python)

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

 

풀이

 최장 증가 부분 수열(LIS)을 활용하여 해결하는 문제다. LIS는 이 링크를 참고하자. LIS를 구하는 방법에는 dp를 사용하는 방법과 이분 탐색을 사용하는 방법이 있다. 이 문제는 dp를 사용하여 해결하면 된다.

 

 A 배열의 각 원소까지 증가 부분 수열을 만들었을 때의 길이를 구한다.

처음 입력 받은 그대로 구한 LIS의 길이

 

 위와 같은 array가 있을 때 dp 배열의 의미는 각 인덱스까지의 증가 부분 수열 중 가장 긴 증가 부분 수열의 길이를 의미한다. 이렇게 한 번 dp를 구하고 이번에는 배열을 뒤집어서 한 번 더 dp를 구해준다. 즉, 처음에는 [5, 2, 1, 4, 3, 5] 배열에 대한 LIS를 구했다면 이번에는 저 배열을 뒤집은 [5, 3, 4, 1, 2, 5] 배열에 대한 LIS를 구하는 것이다. 이렇게 뒤집어서 LIS를 구하면 처음 배열에 대하여 각 인덱스에 대해 최장 감소 부분 수열의 길이를 구할 수 있다.

A 배열을 뒤집어서 구한 LIS의 길이

 

 이렇게 두 개의 dp를 구한 후 각 인덱스에 맞추어 값을 더해준 후 1을 빼준 값(기준이 되는 인덱스의 길이가 2번 더해지기 때문에 1을 빼줘야 한다)이 해당 인덱스를 기준으로 만든 바이토닉 부분 수열의 길이가 된다. 

아래 dp 배열은 기존 배열을 뒤집은 것이기 때문에 그림과 같이 인덱스를 맞추어 길이를 구해줘야 한다.

 

 

코드

# 각 인덱스까지의 LIS의 길이를 구하기 위한 함수 
def findIncrease(array):
    dp = [1 for _ in range(N)]

    for i in range(1, N):
        for j in range(i):
            if array[j] < array[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return dp


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

    increaseDP = findIncrease(A) # 기존 배열에 대한 LIS의 길이를 구한다.
    reverseIncreaseDP = findIncrease(list(reversed(A))) # 배열 A를 뒤집은 후 LIS의 길이를 구한다.

    res = 0
    for i in range(N):
        res = max(res, increaseDP[i] + reverseIncreaseDP[-(i+1)] - 1)

    print(res)