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

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

• https://www.acmicpc.net/problem/1105

---

풀이

방향성 생각

• $O(N^3)$ 바텀업으로도 풀이가 가능해보이긴 한다.
• 탑다운으로 안푼지 오래돼서 연습할겸 탑다운 풀이.
• 같은 인덱스에 / 마지막 값 prev를 들고 / up 상태로 접근

---

전체코드

import sys
sys.setrecursionlimit(10**6)

N = int(input())
arr = list(map(int, input().split()))

dp = {}
def dfs(idx,prev,up):

    # 종료조건
    if idx == N:
        return 0

    # 메모제이션
    state = (idx,prev,up)
    if state in dp:
        return dp[state]

    # 선택 안함
    cnt = dfs(idx+1,prev,up)

    # 초기 예외처리
    if prev == -1:
        cnt = max(cnt,1+dfs(idx+1,arr[idx],1))

    elif up: # 증가상태
        if arr[idx] > prev: # 큰 값이면 선택가능
            cnt = max(cnt,1+dfs(idx+1,arr[idx],1))
        elif arr[idx] < prev: # 작은 값이면 감소 상태로 변경 가능
            cnt = max(cnt,1+dfs(idx+1,arr[idx],0))
    else: # 감소상태
        if arr[idx] < prev: # 작은 값이면 선택가능
            cnt = max(cnt,1+dfs(idx+1,arr[idx],0))

    dp[state] = cnt
    return cnt

print(dfs(0,-1,True))

코멘트

• 풀고보니 좌우로 증가수열 찾아서 어케 푸는 그런게 있더라...