[BOJ]11054(python)

백준 11054(가장 긴 바이토닉 부분 수열) python 풀이입니다

코드 + 풀이 설명

from collections import defaultdict
import sys

input = sys.stdin.readline

def solution():

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

    memo_b = defaultdict(int) #before
    memo_a = defaultdict(int) #after

    for idx in range(N):
        for b_idx in range(0, idx):
            if A[b_idx] < A[idx] and memo_b[b_idx] + 1>= memo_b[idx]:
                memo_b[idx] = memo_b[b_idx] + 1
    
    for idx in range(N - 1, -1, -1):
        for a_idx in range(N - 1, idx - 1, -1): 
            if A[a_idx] < A[idx] and memo_a[a_idx] + 1 >= memo_a[idx]:
                memo_a[idx] = memo_a[a_idx] + 1


    answer = -1
    for idx in range(N):
        t = memo_a[idx] + memo_b[idx] + 1
        if answer < t:
            answer = t

    print(answer)

solution()

• memo_b(before)은 0 ~ 현재 idx 까지 증가 길이를 담았습니다
• memo_a(after) 은 현재 ~ (idx - 1) 까지의 감소 길이를 담았습니다
• memo_b 갱신 : 0 ~ (N - 1)까지 idx 값을 증가시키며 현재 idx까지의 증가 길이는 현재 값보다 작은 수 중 증가 길이가 가장 큰 값으로 갱신합니다
• memo_a 갱신 : (N - 1) ~ 0까지 idx 값을 감소시키며 현재 idx까지의 감소 길이는 현재 값 보다 작은 수 중 감소 길이가 가장 큰 값으로 갱신합니다
• memo_a, memo_b가 모두 갱신되면 0 ~ (N - 1)까지 idx를 돌며 memo_a[idx] + memo_b[idx] + 1(현재값) 값을 구합니다
• 그 값 중 가장 큰 값을 정답처리 합니다

취업은 했어도 플레를 향한 도전은 계속 된다
(골드를 넘어 플레로 갈거야)