[백준/Python] 11054 가장 긴 바이토닉 부분 수열

[백준/Python] 11054 가장 긴 바이토닉 부분 수열

정답 코드 및 설명

전체 코드

N = int(input())
A = list(map(int, input().split()))

increase = [1 for _ in range(N)]
decrease = [1 for _ in range(N)]

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

for i in range(N-1,-1,-1):
    for j in range(N-1, i ,-1):
        if A[j] < A[i]:
            decrease[i] = max(decrease[i], decrease[j] + 1)
        
    
max_length = 0
for i in range(N):
    max_length = max(max_length, increase[i] + decrease[i] - 1)

print(max_length)

설명

가장 긴 바이토닉 부분 수열을 찾기 위해서는 두 단계의 DP 배열을 계산해야한다. 하나는 왼쪽에서 오른쪽으로 진행하며 각 위치에서 가장 긴 증가하는 부분 수열의 길이를 찾는 것이고, 다른 하나는 오른쪽에서 왼쪽으로 진행하며 각 위치에서 가장 긴 감소하는 부분 수열의 길이를 찾는 것이다.

이후, 각 위치에서 가장 긴 증가하는 부분 수열의 길이와 가장 긴 감소하는 부분 수열의 길이를 합친 값에서 1을 빼면(해당 위치 값이 두 수열에서 중복으로 계산되기에), 해당 위치를 기준으로 하는 가장 긴 바이토닉 부분 수열의 길이를 얻을 수 있다.

알고리즘 의사 코드

1. N 과 수열 A 를 입력받는다.
2. 배열 increase 와 decrease 를 길이 N 으로 초기화한다. 이 배열들은 각각 각 위치에서 가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열의 길이를 저장할 것이다.
3. 왼쪽에서 오른쪽으로 진행하며 increase 배열을 채운다.

• 각 i 에 대해서 j < i 인 모든 j 에 대해서 A[j] < A[i] 이면, increase[i] = max(increase[i] , increase[j] + 1) 로 업데이트 한다.

4. 오른쪽에서 왼쪽으로 진행하며 decrease 배열을 채운다

• 각 i 에 대해 j > i 인 모든 j 에 대해서 A[j] < A[i] 이면 decrease[i] = max(decrease[i] , decrease[j] + 1) 로 업데이트 한다.

5. 모든 위치 i 에 대해 increase[i] + decrease[i] - 1 을 계산하고, 이 값들 중 최댓값을 찾는다. 이 최댓값이 가장 긴 바이토닉 부분 수열의 길이이다.