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

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

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

📄 문제개요

• 연속된 가장 긴 바이토닉 수열을 구하는 문제이다.

🤔 문제분석

• 다이나믹 프로그래밍 문제로, 현재 인덱스로부터 증가하는 가장 긴 값을 갱신한다.

1. 처음부터 끝까지 순회하면서, 현재 인덱스로부터 가장 증가하는 긴 값을 dp 배열에 넣는다.
2. 뒤집어서 한번더 증가하닌 긴 값을 dp 배열에 넣는다.

📝 의사코드

1. 수열을 순회하면서, 증가하는 수열의 정보를 갱신한다.
2. 수열을 반대로 뒤집어, 증가하는 수열의 정보를 갱신한다.
3. 2개의 dp 테이블 ( Increase, Decrease ) 배열을 확인해, 조합하여 가장 큰 바이토닉 수열을 찾는다.

💻 코드

import sys
input = sys.stdin.readline

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

# 증가하는 부분 수열의 길이 계산
increase = [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)

# 감소하는 부분 수열의 길이 계산
decrease = [1 for _ in range(N)]
A = A[::-1]
for i in range(N):
    for j in range(i):
        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[N-i-1] - 1)

# 결과 출력
print(max_length)

🎯 피드백 및 개선사항

• 처음에는 dp[start][end]로 2차원 배열로 문제를 접근하였다.
• dp[start][end] = max(dp[start][end-1], dp[start+1][end])로 접근 하였으며, 해당 문제는 연속된 부분수열이라는 조건을 만족 시키지 못한다.
• 위의 문제는 O(N^2)의 시간복잡도로 문제를 해결한다.
• 이분탐색을 통하여 O(Nlog(N)) 으로 시간복잡도를 줄일 수 있다.
• 바이토닉 수열의 정보를 저장하는 임시 배열을 두어, 만약 순회하면서 클경우 뒤에 이어 붙힌다.
• 만약 작다면, 이분탐색으로 해당 인덱스에 자기자신의 값을 갱신함으로서, 그 다음 계산때 항상 최대 값을 갱신하도록 한다.

import sys
from bisect import bisect_left

input = sys.stdin.readline

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

dpr = [1 for _ in range(N)]
dpl = [1 for _ in range(N)]
dpr[0] = 1
dpl[0] = 1

r = [A[0]]
for i in range(1, N):
    if  A[i] > r[-1]:
        r.append(A[i])
    else:
        idx = bisect_left(r, A[i])
        r[idx] = A[i]
        
    dpr[i] = len(r)
    
A = A[::-1]
l = [A[0]]
for i in range(1, N):
    if  A[i] > l[-1]:
        l.append(A[i])
    else:
        idx = bisect_left(l, A[i])
        l[idx] = A[i]

    dpl[i] = len(l)
    
ans = 1
for i in range(N):
    ans = max(ans, dpr[i] + dpl[N-1-i] - 1)
    
print(ans)

❓다른사람은 어떻게 풀었을까?

• 비슷한 조건으로 문제를 해결 하였습니다.