[BOJ/Step15] 11054 : 가장 긴 바이토닉 부분 수열 (Python)

www.acmicpc.net/problem/11054

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

---

바이토닉 부분 수열은 앞 문제 11053번과 비슷하지만 조금 다르다

그냥 양쪽으로 계산해주면 된다

 

k개 원소를 가진 수열

= n번째 숫자 기준으로 0~n까지 가장 긴 증가하는 부분 수열 + n~k-1까지 가장 긴 감소하는 부분 수열 - 1

감소하는 부분 수열을 구하기 힘들기 때문에

수열을 뒤집어서 증가하는 부분 수열을 구한 후 다시 뒤집으면 감소하는 부분 수열이 된다

 

1. 입력받은 수들을 리스트 seq_1에 저장, seq_1을 복사하여 seq_2에 저장, 뒤집어준다

2-1. seq_1와 같은 길이의 t_seq_1을 생성하고 첫번째 요소는 1, 나머지는 0으로 채운다

       => seq_1[n]까지의 가장 긴 증가하는 부분 수열의 개수를 리스트 t_seq_1[n]에 저장할 것

2-2. seq_2와 같은 길이의 t_seq_2을 생성하고 첫번째 요소는 1, 나머지는 0으로 채운다

        => seq_2[n]까지의 가장 긴 증가하는 부분 수열의 개수를 리스트 t_seq_2[n]에 저장할 것

3. for문으로 t_seq_1[1] ~ t_seq_1[n-1] / t_seq_2[1] ~ t_seq_2[n-1] 까지 계산

  3-1. 리스트 a, b에 0을 저장

  3-2. for문으로 a에 seq_1[0] ~ seq_1[n-1] 중 seq_1[n]보다 작은 숫자들의 t_seq_1[n]을 저장

          for문으로 b에 seq_2[0] ~ seq_2[n-1] 중 seq_2[n]보다 작은 숫자들의 t_seq_2[n]을 저장

  3-3. a의 최댓값 + 1을 t_seq_1[n]에 저장 / b의 최댓값 + 1을 t_seq_2[n]에 저장

4. t_seq_2를 뒤집는다

5. t_seq에 t_seq_1 + t_seq_2 -1 을 저장한다

6. t_seq의 최댓값을 출력

세부 설명은 11053번

# 11054.py

n = int(input())
seq_1 = [i for i in map(int, input().split())]
t_seq_1 = [1] + [0 for _ in range(n-1)]
seq_2 = [i for i in seq_1]
seq_2.reverse()
t_seq_2 = [1] + [0 for _ in range(n-1)]

for i in range(1, n):
    a = [0]
    b = [0]
    for j in range(i):
        if seq_1[j] < seq_1[i]:
            a.append(t_seq_1[j])
        if seq_2[j] < seq_2[i]:
            b.append(t_seq_2[j])
    t_seq_1[i] = max(a) + 1
    t_seq_2[i] = max(b) + 1

t_seq_2.reverse()
t_seq = [t_seq_1[i] + t_seq_2[i] - 1 for i in range(n)]
print(max(t_seq))