백준 11054 파이썬 - 가장 긴 바이토닉 부분 수열 - 동적 계획법, LIS

백준 11054 파이썬

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

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

이번 문제는 이전에 풀었던 [CS/알고리즘] - 백준 11053 파이썬 - 가장 긴 증가하는 부분 수열 - 동적 계획법, LIS 문제의 응용이다. 바이토닉 부분 수열을 가장 긴 증가하고 감소하는 부분 수열이다. 즉 이전에 풀었던 LIS 문제에서 배열의 각 위치에서의 최대 증가하는 부분 수열을 주어진 배열과 주어진 배열을 뒤집은 배열 2가지를 구해서 해결할 수 있다.

 

 

 

Python 풀이

import sys
read = sys.stdin.readline

N = int(read())
A = list(map(int, read().split()))
forward = [0] * N
backward = [0] * N

def calc(reverse=False):
    if reverse:
        temp = [A[-1]]
        seq = backward
        r = range(N-1, -1, -1)
    else:
        temp = [A[0]]
        seq = forward
        r = range(N)

    for i in r:
        if temp[-1] < A[i]:
            temp.append(A[i])
        else:
            idx = 0
            for j in range(len(temp)):
                if temp[j] < A[i]:
                    idx += 1
                else:
                    temp[idx] = A[i]
                    break
        seq[i] = len(temp)

calc()
calc(True)

res = -1
for i in range(N):
    res = max(res, forward[i] + backward[i])
print(res-1)

• calc 함수는 LIS를 구하는 함수이다.
  • reverse flag를 사용하면 배열을 뒤에서부터 순회해서 가장 긴 감소하는 부분 수열을 구할 수 있다.
• 각각 증가하고 감소하는 부분 수열을 구하고 같은 위치의 값을 더한 값 중 최대값이 가장 긴 바이토닉 수열이 된다.
• 위치가 겹쳐 중복되는 1을 빼줘야한다.

저작자표시비영리변경금지