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

💻 문제 - G4

주어진 수열에 대해 증가하는 수열과 감소하는 수열의 길이를 각각 구한다: dp_inc, dp_dec.
모든 Sk에 대해 가장 긴 바이토닉 수열의 길이를 구하여 최댓값을 구한다.

👉 제출 코드

N = int(input())
arr = list(map(int, input().split()))
arr_rev = arr[::-1]
dp_inc = [1] * N
dp_dec = [1] * N

for i in range(N):
    for j in range(i):
        if arr[j] < arr[i]:
            dp_inc[i] = max(dp_inc[j]+1, dp_inc[i])
        if arr_rev[j] < arr_rev[i]:
            dp_dec[i] = max(dp_dec[j]+1, dp_dec[i])
            
result = [0] * N
for i in range(N):
    result[i] = dp_inc[i] + dp_dec[N-1-i] - 1
           
print(max(result))

result를 저장하면서 위치대로 Sk가 중복되므로 1을 뺀다.

🙏 다른 사람의 풀이 보기

N = int(input())
arr = list(map(int, input().split()))
dp_inc = [1] * N
dp_dec = [1] * N

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

for i in range(N-1, -1, -1):
    for j in range(N-1, i, -1):
        if arr_rev[j] < arr_rev[i]:
            dp_dec[i] = max(dp_dec[j]+1, dp_dec[i])
            
result = [0] * N
for i in range(N):
    result[i] = dp_inc[i] + dp_dec[i] - 1
           
print(max(result))

reverse한 배열을 사용하지 않고 for문을 역방향으로 돌려 감소하는 부분 수열을 구한다.