[BOJ, Python] 11054번_가장 긴 바이토닉 부분 수열

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기

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

문제를 본 처음에는 아래와 같이 풀이 방식을 생각했다.

1. 각 위치에는 Ai를 k로 잡았을 때의 가장 긴 수열을 길이를 저장
2. Ai를 k로 잡는다면 2가지 경우를 찾으면 됨

• k의 왼쪽 부분 수열: 오름차순이면 최댓값이 k보다 작은 수열
• k의 오른쪽 부분 수열: 내림차순이면 최댓값이 k보다 작은 수열
  3. Ai의 값은 (k의 왼쪽 부분 수열의 길이) + (k의 오른쪽 부분 수열의 길이) + 1이다.

그러나 이 풀이에는 허점이 있었다. 왼쪽, 오른쪽으로 나눈 부분 수열 또한 다시 부분 수열로 나뉠 수 있다는 것이다.
어떻게든 이 풀이방식을 고집한다면 문제를 풀 수 있을거 같았지만 문제가 요구하는 방식이 아니고, 이런 경우 시간복잡도가 일정 기준 이상으로 커질 것이라고 생각해서 이 풀이 방식은 기각했다.

기존 풀이 방식 중 두 개의 수열로 나눠서 문제를 푸는 방식을 그대로 유지해 새로운 풀이 방식을 생각했다.

이쯤에서 다시 한 번 문제를 정리해봤다.

문제 정리

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

기존 풀이 방식 중 두 개의 수열로 나눠서 문제를 푸는 방식을 그대로 유지해 새로운 풀이 방식을 생각했다.

증가하는 수열과 감소하는 수열 두 가지로 나누어서 생각해보자

• 주어진 수열: {1, 5, 2, 1, 4, 3, 4, 5, 2, 1}
  • 증가하는 수열 길이: [1, 2, 2, 1, 3, 3, 4, 5, 2, 1]
  • 감소하는 수열 길이: [1, 5, 2, 1, 4, 3, 3, 3, 2, 1]

각 인덱스별로 (증가하는 수열 길이 + 감소하는 수열 길이의 합)이 가장 큰 지점이 바이토닉 수열의 Sk 원소가 된다.

즉, 주어진 수열에서의 바이토닉 수열은 1,2,3,4,5,2,1가 되며, Sk는 5가 된다.

문제 풀이 방식을 정리했으니 이를 코드로 구현해보자.

풀이 코드

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
A = list(map(int, input().split()))
reverse_A = A[::-1]

increase = [1]*N # 가장 긴 증가하는 부분 수열
decrease = [1]*N # 가장 긴 감소하는 부분 수열

for i in range(N):
    for j in range(i):
        if A[i] > A[j]:
            increase[i] = max(increase[i], increase[j]+1)
        if reverse_A[i] > reverse_A[j]:
            decrease[i] = max(decrease[i], decrease[j]+1)

result = [0]*N
for i in range(N):
    result[i] = increase[i] + decrease[N-i-1] - 1

print(max(result))

풀이는 간단하다.
언급 했던것처럼 증가하는 수열, 감소하는 수열의 길이를 저장할 리스트를 2개 만들어 준다.
이후 2중 반복문을 통해 각 인덱스에 대한 증가하는 수열의 길이, 감소하는 수열의 길이를 탐색해 저장한다.
모든 인덱스에 대해 탐색한 뒤 각 리스트를 돌며 증가하는 수열의 길이와 감소하는 수열의 길이를 더해준다.

이때 -1을 해주는데 인덱스 값이 겹치기 때문이다.

길이 중 가장 큰 값이 정답이 된다.