[Python] 백준 / gold / 11054 : 가장 긴 바이토닉 부분 수열

문제 링크 : https://www.acmicpc.net/problem/11054

다이나믹 프로그래밍 문제. 이런 생각의 흐름으로 문제를 풀었다.

1. 여러가지 예시들을 떠올려봤다. 예를들어, A = [1, 5, 6, 2, 3, 4, 5] 라는 수열이 있다면, A[0] = 1 의 뒤에서 당장 눈앞의 수인 A[1] = 5 를 선택해도 [1, 5, 6] 오름차순을 만들 수 있지만, 눈 앞의 이득을 포기하고 A[3] = 2 를 선택하면 [1, 2, 3, 4, 5] 를 만들 수 있다.

2. 당장 눈 앞의 이득을 챙겨서 푸는 것은 그리디 알고리즘, 눈 앞의 이득을 포기하더라도 뒤에서 더 큰 이득을 챙길 수 있다면 다이나믹 프로그래밍으로 기억을 해뒀었다 -> 다이나믹 프로그래밍으로 풀어야겠다고 생각.

3. DP 로 풀기로 마음 먹었으니, DP table 을 1차원으로 설계할 건지, 2차원으로 설계할 건지 고민했다. 예전에 증가하는 부분 수열을 구할 때 1차원 DP 로 푸는 공부를 했던 기억이 났다 -> 1차원 DP table 설계를 해야겠다고 생각.

4. upDP[i] = (수열의 처음부터 i 까지 살펴봤을 때, 가장 크게 만들 수 있는 오름차순 부분 수열의 크기)
   downDP[i] = (i 부터 수열의 끝까지 살펴볼 때, 가장 크게 만들 수 있는 내림차순 부분 수열의 크기)
   로 두 개의 dp table 을 설계.

5. 파이썬의 zip 을 활용해서 upDP 와 downDP 를 결합

6. upDP[i] 와 downDP[i] 에서 i 를 두 번 카운팅 하므로 중복된 1을 빼서 정답 출력

파이썬 코드

import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
upDP = [1] * N
downDP = [1] * N

for i in range(1, N):
    max_value = 0
    for j in range(i):
        if A[j] < A[i]:
            max_value = max(max_value, upDP[j])
    upDP[i] += max_value

for i in reversed(range(N-1)):
    max_value = 0
    for j in range(i+1, N):
        if A[i] > A[j]:
            max_value = max(max_value, downDP[j])
    downDP[i] += max_value

dp = [x+y for x, y in zip(upDP, downDP)]
print(max(dp) - 1)