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

가장 긴 바이토닉 부분 수열

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

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

---

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제 입력 1 

10
1 5 2 1 4 3 4 5 2 1

예제 출력 1 

7

힌트

예제의 경우 {1 5 2 1 4 3 4 5 2 1}이 가장 긴 바이토닉 부분 수열이다.

---

코드

n = int(input())
a = list(map(int, input().split()))
inc = [1] * n
rev_inc = [1] * n
tmp = 0

for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            inc[i] = max(inc[i], inc[j] + 1)
        if a[-(i+1)] > a[-(j+1)]:
            rev_inc[-(i+1)] = max(rev_inc[-(i+1)], rev_inc[-(j+1)] + 1)
            
for k in range(n):
    if tmp < inc[k] + rev_inc[k]:
        tmp = inc[k] + rev_inc[k]
else:
    print(tmp - 1)

풀이

해당 문제는 11053번을 응용하는 문제라고 볼 수 있다. 해당 문제를 풀 때 큰 힌트를 얻었던 부분은 문제 예시로 나와있는 {10, 20, 30, 25, 20} 해당 수열이다. 해당 수열을 보면 0번째 인덱스를 기준으로 증가하는 부분 수열의 길이(inc)를 구하고, -1번째를 기준으로 증가하는 부분 수열의 길이(rev_inc)를 구하고 증가하는 부분 수열의 길이를 구한 두 리스트 값의 합의 크기를 이용해 가장 긴 바이토닉 부분 수열의 길이를 구하면 되는 것이다.

코드를 통해 살펴보자.

입력 및 배열 생성을 살펴보자. 우선 0번째 인덱스, 즉 앞에서부터 증가하는 부분 수열의 길이를 구할 리스트를 inc, -1번째 인덱스, 즉 뒤에서부터 증가하는 부분 수열의 길이를 구할 리스트를 rev_inc를 생성한다. 이 때 1로 초기화하는 이유는 최소 부분 수열은 자기 자신만을 부분 수열로 가지기 때문이다.

이제 for문을 살펴보자. 이중 for문을 이용해 바깥 for문에서의 인덱스 값(ex. i = 4)와 안쪽 for문에서의 인덱스 값(ex, j = 1, 2, 3)을 돌면서 i번째 인덱스 값에서의 가장 긴 증가하는 부분 수열의 길이를 저장한다.

if문을 살펴보자. 이 때 1번째 if문은 앞에서부터 구한 가장 긴 증가하는 부분 수열의 길이, 2번째 if문은 뒤에서부터 구한 가장 긴 증가하는 부분 수열의 길이를 저장한다. (파이썬은 앞은 0번째 인덱스부터 시작하며, 뒤는 -1번째부터 시작함을 유의하라.)마지막 for문은 두 리스트를 이용하여 가장 긴 바이토닉 부분 수열을 구하는 것이다. 각 인덱스마다 두 리스트 값의 합을 구해서 최댓값을 tmp에 갱신하여 저장한다. 마지막에 tmp - 1을 해주는 이유는 중복 카운트되는 횟수를 제외해주기 위해서이다. 즉, {10, 20, 30, 25, 20}에서는 inc = [1, 2, 3, 3, 2], rev_inc = [1, 1, 3, 2, 1]인데 최종 tmp = 6(3+3)이 되지만 30의 값이 2번 카운트되기 때문에 1을 빼주는 것이다.