문제 출처 : https://www.acmicpc.net/problem/11054

---

어제 포스팅했던 백준 11053번 | 실버 2 | 가장 긴 증가하는 부분 수열 | Python의 다음 문제이다.
난이도가 실버 2에서 바로 골드 4로 올라서였을까 많이 안붙어보고 쫄아서 금방 답을 봤던 것 같다.
그러나 막상 답을 보니 쫄았던게 맞는 것 같다.

전 문제를 200% 이해했다면 풀었을 수도 있을 것 같다.

문제 파악

바이토닉 수열이라는 개념이 나온다.

바이토닉 수열은 증가하다가 감소하는 꼴의 수열이라고 알려준다.
증가 -> 감소 -> 증가 이런식은 안되고 산 모양처럼 꼭대기가 존재하고, 그것을 기준으로 좌는 증가수열, 우는 감소수열이어야 한다.

그래서 문제는 어떠한 수열이 주어졌을 때, 그 수열에서 가장 긴 바이토닉수열의 길이를 출력해야 한다.

---

문제 풀이의 핵심은 전에 풀었던 로직의 재사용이었다.
증가하다가 감소하니
증가 dp, 감소 dp를 두개 만들어서 합쳐야 했다.
증가 dp는 전 문제 로직 그대로 사용하면 됐고

# 1. 왼쪽에서부터 LIS
dp_increase = [1] * N
for i in range(N):
    for j in range(i):
        if A[i] > A[j]:
            dp_increase[i] = max(dp_increase[i],dp_increase[j]+1)

감소 로직은 range에서 감소에 대한 반복문에 대한 이해가 조금 필요했다.
0~N-1 인덱스 리스트가 있을 때 감소로 N-1 에서 i+1 까지 가기 위해서는
for i in range(N-1,i,-1): 의 꼴로 코드를 작성해야 한다.

감소 dp 코드

# 2. 오른쪽에서부터 LIS (앞에서보면 감소)
dp_decrease = [1] * N
for i in range(N-1, -1, -1): # i : N-1 ~ 0 까지 1씩 감소
    for j in range(N-1, i, -1): # j : N-1 ~ i+1 까지 1씩 감소
        if A[i] > A[j]:
            dp_decrease[i] = max(dp_decrease[i],dp_decrease[j]+1)

---

마지막은 이 만든 dp코드를 합치는데 가운데 i가 중복되니 -1을 해주는 포인트가 있었다.

# 3. i를 꼭대기로 하는 바이토닉 수열 길이 계산
answer = 0
for i in range(N):
    answer = max(answer ,dp_increase[i] + dp_decrease[i] -1)

---

전체 코드

import sys
input = sys.stdin.readline

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

# dp[i] = i번째를 마지막 인수로 가지면서 바이토닉 수열이면서 가장 긴 수열의 길이


# 1. 왼쪽에서부터 LIS
dp_increase = [1] * N
for i in range(N):
    for j in range(i):
        if A[i] > A[j]:
            dp_increase[i] = max(dp_increase[i],dp_increase[j]+1)


# 2. 오른쪽에서부터 LIS (앞에서보면 감소)
dp_decrease = [1] * N
for i in range(N-1, -1, -1): # i : N-1 ~ 0 까지 1씩 감소
    for j in range(N-1, i, -1): # j : N-1 ~ i+1 까지 1씩 감소
        if A[i] > A[j]:
            dp_decrease[i] = max(dp_decrease[i],dp_decrease[j]+1)

# 3. i를 꼭대기로 하는 바이토닉 수열 길이 계산
answer = 0
for i in range(N):
    answer = max(answer ,dp_increase[i] + dp_decrease[i] -1)

print(answer)

백준 플랫폼은 꽤나 친절하다. 단계별로 문제를 제시하니 갑자기 어려운 문제가 나왔을 때는 전 문제의 로직을 떠올려보자