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

알고리즘 유형 : DP(Dynamic Programming)
풀이 참고 없이 스스로 풀었나요? : O

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

import sys
input = sys.stdin.readline

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

LBS, LIS, LDS = [[1] * N for _ in range(3)]

# LIS, LDS 구하기(arr의 모든 수에 대해, 그 수가 마지막 수일 때의 LIS, LDS 값들을 LIS, LDS 리스트에 채우기)
# 0번째부터 N-1번째까지 모든 수에 대해, 그 수가 마지막인 부분 수열일 때, LIS값은 그 수 이전의 값 중 그보다 작은 수의
# LIS 값 중 최대인 값에 +1을 한 것
for idx in range(1, N):
    for i in range(idx):
        if arr[i] < arr[idx]:
            LIS[idx] = max(LIS[idx], LIS[i] + 1)

for idx in range(-2, -N - 1, -1):
    for i in range(-1, idx, -1):
        if arr[i] < arr[idx]:
            LDS[idx] = max(LDS[idx], LDS[i] + 1)

# 모든 수에 대해, 그 수가 기준 수일 경우의 LBS 값들 구해서 LBS 리스트에 채우기
for idx in range(N):
    left = 0
    right = 0
    
    if idx > 0:
        for i in range(idx):
            if arr[i] >= arr[idx]:
                continue
            left = max(left, LIS[i])
    if idx < N - 1:
        for i in range(idx + 1, N):
            if arr[i] >= arr[idx]:
                continue
            right = max(right, LDS[i])
    
    LBS[idx] = left + right + 1

print(max(LBS))

풀이 요약

LIS 알고리즘 응용 문제이다
LIS : Longest Incresing Sequence, 가장 긴 증가하는 부분 수열

1. 입력받은 arr의 모든 원소(수)에 대한 LIS, LDS를 DP로 구해놓기
2. 최종적으로 구하려는 것은 LBS 리스트에서 최대인 값
3. LBS 리스트를 구해야 하는데, LBS[i]는 arr[i]가 기준 수일 때의 LBS 값을 의미함. for문으로 돌면서, 기준 수에 대해, 그 수보다 작은 arr[i] 중 기준 수보다 작은 arr[i]에 대해, LIS[i] + 1 또는 LDS[i] + 1 가 가장 큰 것을 left, right에 저장. LBS[idx] 는 기준 수 하나와, 양쪽 LIS, LDS 를 더한 값임
4. print(max(LBS))

배운 점, 부족했던 점

배운 점

• LBS, LIS, LDS 에 똑같이 N 크기의 리스트를 초기화하는 코드를 한 줄로 간략하게 줄임

부족했던 점

• 특정 기준 수에 대해 LBS 조건을 만족하는 왼쪽 부분의 LIS를 구할 때, LIS 중 가장 큰 수가 기준 수보다 작은 것들만 골라서 max 연산해내면 되는데, 이걸 생각못하고 LIS, LDS 함수 따로 만들고 LBS 리스트 for 돌면서, 돌 때마다 기준 수보다 작은 arr sequence를 새로 정의해서 인자로 넘겨주고 LIS, LDS를 돌려줘버려서 시간 초과남.

• LIS 알고리즘 이해도 부족. 모든 기준 수에 대해 LIS, LDS는 최소 1인데, 첨에 초기화할 때 1로 초기화하면 될 것을, 모르고 0으로 초기화 후, 나중에 length = 1 을 이용해서 LIS, LDS 리스트를 채우는 비효율적인 코드를 작성했었음