[백준] 11054 가장 긴 바이토닉 부분 수열, python

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

11054번: 가장 긴 바이토닉 부분 수열

N = int(input())
A = list(map(int, input().split()))
dp_asc = [0 for _ in range(N)]
dp_desc = [0 for _ in range(N)]

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

for i in range(N - 2, -1, -1):
    for j in range(i + 1, N):
        if A[j] < A[i]:
            dp_desc[i] = max(dp_desc[i], dp_desc[j] + 1)

ans = 0
for i in range(N):
    if ans < dp_asc[i] + dp_desc[i]:
        ans = dp_asc[i] + dp_desc[i]
print(ans + 1)

다이나믹 프로그래밍을 사용하는 문제이다.

바이토닉 수열은 오름차순과 내림차순이 한번씩 있는 수열인데, 오름차순, 내림차순은 한번씩만 있어도 되고, 두개다 있는경우 오름차순이 먼저 나와야한다. 

여기서 dynamic programming은 오름차순, 내림차순에서 가장 긴 부분을 구하는 곳에서 사용된다. 처음부터 마지막까지 순회하면서 오름차순인지 확인해야하는데, 수열이 [1,3,2,5,3,4,5]로 주어졌을때 오름차순의 최대 길이를 memoization하면 [0,1,1,2,3,4,5]가 나온다. 내림차순은 마지막에서 처음까지 역순으로 오름차순 길이를 구하면 된다.

각 인덱스마다 오름차순과 내림차순의 최대 길이가 나오게 되고 두값을 더한 것 중에 가장 큰 값을 찾으면 된다. 이때 원하는 값보다 1이 적게 나온다. 시작값을 0으로 시작했기 때문에 보정을 해줘야한다. 시작값을 1로 시작하면 1이 크게 나온다. 이는 오름차순, 내림차순 같은 최고점을 찍기 때문에 생기는 문제이다.

---

이중 반복문을 풀어서 좀더 쉽게 풀수 있을거같은데 너무 오래 걸려서 여기서 그만두었다.

[0 for _ in range(N)] 이 [0] * N 보다 속도가 빠른걸 알게 되었다. (이전에 알고있었는지 모르겠는데 다시 알게 되었다)

---

골드 2도 찍었다~~~ 야호