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

*문제 출처는 백준에 있습니다.

문제 제목: 가장 긴 바이토닉 부분 수열 / 11054번 (골드 4단계)

문제 사이트: https://www.acmicpc.net/problem/11054

 

문제 설명

---

나의 풀이

n = int(input())
s = list(map(int, input().split()))

# 각 인덱스까지의 가장 긴 증가하는 부분 수열의 길이를 저장
increase_dp = [1] * n
for i in range(n):
    for j in range(i):
        if s[i] > s[j]:
            increase_dp[i] = max(increase_dp[i], increase_dp[j] + 1)

# 각 인덱스부터의 가장 긴 감소하는 부분 수열의 길이를 저장
decrease_dp = [1] * n
for i in range(n - 1, -1, -1):
    for j in range(i + 1, n):
        if s[i] > s[j]:
            decrease_dp[i] = max(decrease_dp[i], decrease_dp[j] + 1)

# 가장 긴 바이토닉 수열의 길이를 구함
max_length = 0
for i in range(n):
    # 바이토닉 수열의 길이는 increase_dp[i] + decrease_dp[i] - 1
    max_length = max(max_length, increase_dp[i] + decrease_dp[i] - 1)

print(max_length)

"""
예제 출력

각 인덱스까지의 가장 긴 증가하는 부분 수열의 길이를 저장
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 2, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 2, 2, 1, 1, 1, 1, 1, 1, 1]
[1, 2, 2, 1, 1, 1, 1, 1, 1, 1]
[1, 2, 2, 1, 3, 1, 1, 1, 1, 1]
[1, 2, 2, 1, 3, 3, 1, 1, 1, 1]
[1, 2, 2, 1, 3, 3, 4, 1, 1, 1]
[1, 2, 2, 1, 3, 3, 4, 5, 1, 1]
[1, 2, 2, 1, 3, 3, 4, 5, 2, 1]
[1, 2, 2, 1, 3, 3, 4, 5, 2, 1]

각 인덱스부터의 가장 긴 감소하는 부분 수열의 길이를 저장
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 2, 1]
[1, 1, 1, 1, 1, 1, 1, 3, 2, 1]
[1, 1, 1, 1, 1, 1, 3, 3, 2, 1]
[1, 1, 1, 1, 1, 3, 3, 3, 2, 1]
[1, 1, 1, 1, 4, 3, 3, 3, 2, 1]
[1, 1, 1, 1, 4, 3, 3, 3, 2, 1]
[1, 1, 2, 1, 4, 3, 3, 3, 2, 1]
[1, 5, 2, 1, 4, 3, 3, 3, 2, 1]
[1, 5, 2, 1, 4, 3, 3, 3, 2, 1]

바이토닉 수열의 길이는 increase_dp[i] + decrease_dp[i] - 1
"""

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/175

[알고리즘] 동적계획법(Dynamic Programming)