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

DP 문제

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

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

 

▪︎  내 코드

import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

def bitonic(n, arr):
    dp = [1] * n
    dp2 = [1] * n

    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    for i in range(n - 2, -1, -1):
        for j in range(i, n):
             if arr[i] > arr[j]:
                 dp2[i] = max(dp2[i], dp2[j] + 1)

    ans = []
    for i in range(n):
        ans.append((dp[i] + dp2[i]))
    print(max(ans) - 1)
    
bitonic(n, arr)

 

백준 11053번 (가장 긴 증가하는 부분 수열)의 점화식을 생각하며 푸니까 금방 풀렸다.

첫번째로, 순방향으로 for문을 돌며 해당 i번째까지의 가장 긴 증가하는 부분 수열의 길이를 dp 배열에 저장한다.

두번째로, 역방향으로 for문을 돌며 해당 i번째까지의 가장 긴 증가하는 부분 수열의 길이를 dp2 배열에 저장한다.

마지막 for문에서는 ans 배열에 dp 배열과 dp2 배열의 각 index를  합한 값을 넣어준다.

여기서 max(ans) - 1이 가장 긴 바이토닉 부분 수열의 값이 된다. 중복되는 값이 있기 때문에 -1을 해주었다.

 

느낀점 : 사실 그냥 빨리 풀어버리고 싶어서 대충 로직 생각하고 짠 뒤 반례만 몇개 찾아서 반례에 맞게 답이 도출될 수 있도록 코드를 수정하는 식으로 이 문제를 풀었다. 그래서 난 당연히 틀릴줄 알았는데 맞아서 놀라웠다 .. 담엔 좀 더 정성 들여서 풀어야겠다