[Python Algorithm] 가장 긴 바이토닉 부분 수열 BOJ #11054

문제

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

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

 

내 문제 풀이

import sys

n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().strip().split()))
r_nums = list(reversed(nums))
memory1 = [0 for _ in range(n)]
memory2 = [0 for _ in range(n)]
answer = 0

memory1[0] = 1
for i in range(1, n):
    maxi = 0
    for j in range(i):
        if nums[j] < nums[i]:
            maxi = max(maxi, memory1[j])
    memory1[i] = maxi + 1

memory2[0] = 1
for i in range(1, n):
    maxi = 0
    for j in range(i):
        if r_nums[j] < r_nums[i]:
            maxi = max(maxi, memory2[j])
    memory2[i] = maxi + 1
memory2 = list(reversed(memory2))

for i in range(n):
    answer = max(answer, memory1[i] + memory2[i])

print(answer - 1)

👉 DP 문제

memory1, memory2를 만들고,

각각 앞에서부터 시작하는 가장 긴 부분 수열, 뒤에서부터 시작하는 가장 긴 부분 수열을 구했다.

그리고 memory1과 memory2를 비교하며 같은 인덱스의 요소 합이 가장 큰 것을

가장 긴 바이토닉 부분 수열의 꼭지점이라고 판단해주었다.

 

💡 피드백

• 부분 수열을 구하는 방법만 알고 있다면 굉장히 쉽게 풀 수 있는 문제였다.