[백준/python] 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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

정답

import sys
input = sys.stdin.readline

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

inc = [1] * N
dec = [1] * N

for i in range(N):
    for j in range(i):
        if A[i] > A[j] and inc[i] <= inc[j]:
            inc[i] = 1 + inc[j]

for i in range(N-1, -1, -1):
    for j in range(N - 1, i, -1):
        if A[i] > A[j] and dec[i] <= dec[j]:
            dec[i] = 1 + dec[j]

answer = [sum(s)-1 for s in zip(inc, dec)]
print(max(answer))

---

오른쪽으로 오름차순인 부분 수열을 구하고 왼쪽 방향으로 오름차순인 부분 수열을 구한다. 

inc에는 해당 인덱스에 도달하기까지 오른쪽 방향으로 오름차순이 되는 부분 수열의 최대 길이를 저장하고

dec에는 해당 인덱스에 도달하기까지 왼쪽 방향으로 오름차순이 되는 부분 수열의 최대 길이를 저장한다.

dec의 경우 바꿔말하면 해당 인덱스부터 감소하는 부분 수열이 된다.

 

예를 들어, {1, 3, 5}의 수열에서 5에 도달하기까지 오른쪽 방향으로 오름차순이 되는 부분 수열은

{1, 5}, {3, 5}, {1, 3, 5}가 있다.

이 중 {1, 3, 5}의 길이가 더 길기 때문에 5의 인덱스 2 즉, inc[2]에 3이 저장된다.

 

inc를 구하는 경우와 dec를 구하는 경우로 중첩 for문을 2번 반복한다.

 

for i in range(N):
    for j in range(i):
        if A[i] > A[j] and inc[i] <= inc[j]:
            inc[i] = 1 + inc[j]

inc를 구하는 경우로 작은 인덱스부터 시작한다.

A[i]에 도달하기위해 0부터 i-1까지의 인덱스 j를 살펴본다.

inc에는 해당 인덱스에 도달하기까지 거쳐가는 인덱스 개수의 최대값이 담겨있다.

A[j]가 A[i]보다 작아야 오름차순이 완성되고 inc[j]가 inc[i]보다 크거나 같아야 가장 많이 거쳐가므로

해당 조건을 만족할 때 inc[i]에 j에 도달하기까지 거쳐간 인덱스 개수의 최대값 inc[j]에 1을 더한 값을 저장한다.

여기서 더하는 1은 A[i]를 의미한다.

 

for i in range(N-1, -1, -1):
    for j in range(N - 1, i, -1):
        if A[i] > A[j] and dec[i] <= dec[j]:
            dec[i] = 1 + dec[j]

dec도 마찬가지로, 인덱스를 거꾸로 살펴보면 된다.

 

answer = [sum(s)-1 for s in zip(inc, dec)]
print(max(answer))

inc와 dec에는 해당 인덱스에 도달하기까지 거쳐가는 인덱스의 최대개수가 담겨있으므로

같은 인덱스끼리 더해주면 오름차순에서 내림차순으로 가는 인덱스 개수가 나온다.

zip을 이용하여 같은 인덱스끼리 더해주고 1을 빼 answer에 저장한다.

여기서 1을 빼주는 이유는 해당 인덱스에 도착했을 때를 inc와 dec에서 각각 한번씩 세주었기 때문이다.

 

마지막으로 리스트 answer의 최대값을 출력한다.