[DP/동적계획법] 백준 11054 가장 긴 바이토닉 부분 수열 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

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

 

 

 

2. 문제 풀이

가장 긴 바이토닉 부분 수열을 구하는 문제입니다.

 

[ 1 3 2 1 4 2 2 1 ] => [ 1 2 4 2 1 ]

 바이토닉 부분 수열은 '증가수열 + 감소수열'의 형태로, 증가하다가 감소하는 수열입니다. 유의할 점은 증가 수열 또는 감소 수열만 있어도 바이토닉 부분 수열입니다. 굳이 꼭 증가하다 감소하진 않아도 됩니다.

 

 

2022.04.12 - [Algorithm] - [DP/동적계획법] 백준 11053 가장 긴 증가하는 부분 수열 - 파이썬(Python)

2022.04.14 - [Algorithm] - [DP/동적계획법] 백준 11722 가장 긴 감소하는 부분 수열 - 파이썬(Python)

 위 두 문제를 합친 문제입니다. 가장 긴 증가 혹은 감소 부분 수열을 찾는 방법은 위 글을 참조해주시기 바랍니다.

 

 

 

3. 코드

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

# DP로 가장 긴 증가 및 감소 부분 수열 찾기
increase = [1]*N
decrease = [1]*N
for i in range(N):
    for j in range(i):
        # 더 작은 이전 원소 발견
        if A[i] > A[j]:
            # 이전 원소에 +1한 게 더 길면 갱신
            increase[i] = max(increase[i], increase[j]+1)

        # 더 큰 이전 원소 발견
        if A[-i] > A[-j]:
            decrease[-i] = max(decrease[-i], decrease[-j]+1)

print(A)
print(increase)
print(decrease)

# 가장 긴 바이토닉 수열의 길이 찾기
maxlen = 0
for i in range(N):
    maxlen = max(maxlen, increase[i]+decrease[i]-1)
print(maxlen)

 맨 처음에는 음수 인덱스를 사용해서 한 번에 최장 증가/감소 수열을 구하려고 했습니다.

 

 하지만 -0 = 0 이기 때문에 인덱스 오류도 있고, i지점까지의 최장 감소수열도 아니기 때문에 예제만 맞았습니다.

 

 

# 입력
N = int(input())
A = list(map(int, input().split()))
reverse_A = A[::-1]

# DP로 가장 긴 증가 및 감소 부분 수열 찾기
increase = [1]*N
decrease = [1]*N
for i in range(N):
    for j in range(i):
        # 더 작은 이전 원소 발견
        if A[i] > A[j]:
            # 이전 원소에 +1한 게 더 길면 갱신
            increase[i] = max(increase[i], increase[j]+1)

        # 더 큰 이전 원소 발견
        if reverse_A[i] > reverse_A[j]:
            decrease[i] = max(decrease[i], decrease[j]+1)

# 가장 긴 바이토닉 수열의 길이 찾기
maxlen = 0
for i in range(N):
    maxlen = max(maxlen, increase[i]+decrease[N-i-1]-1)
print(maxlen)

 정답 코드는 위 코드입니다. 최장 감소수열을 구하기 위해 아예 reverse_A를 따로 만들었습니다. 이후, 'i까지의 최장 증가수열'과 'i~N까지의 최장 감소수열'을 더해서 '최장 바이토닉 수열의 길이'를 찾았습니다.