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

 

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

v

문제

수열 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}이 가장 긴 바이토닉 부분 수열이다.

---

문제 풀이

 

 

입력의 크기가 최대 1000개 이므로 시간 복잡도 O(N^2) 에서도 충분히 여유롭다.

 

그래서 생각한 방법이 이중 for문을 통해 해당 위치가 최고점이라 생각했을 때, 왼쪽에서부터 얼마나 오랫동안 증가했는지,

오른쪽에서부터 얼마나 오랫동안 감소했는지의 값을 저장하기로 생각했다.

 

순차적으로 값을 저장하고 해당 값을 이용하여 다음 배열에 참조값으로 사용할 수 있으므로 

다이나믹 프로그래밍, 즉 Bottom-up 방식으로 구현했다.

 

구현을 마친 뒤 배열에서 증가하는 길이와 감소하는 길이를 합친 값이 가장 큰 원소를 기준으로 왼쪽은 증가, 오른쪽은 감소로 나타날 것이다.

 

그러므로 해당 원소까지 개수를 세어 값을 출력하면 된다.

 

---

 

코드

 

N = int(input())
A = list(map(int, input().split()))
dp = [[0, 0] for _ in range(N)]
# [증가,감소]
for i in range(1, N):		#증가하는 길이 저장
    for j in range(i):
        if A[j] < A[i]:
            if dp[i][0] < dp[j][0] + 1:
                dp[i][0] = dp[j][0]+1

for i in range(N-2, -1, -1):	#감소하는 길이 저장
    for j in range(N-1, i, -1):
        if A[j] < A[i]:
            if dp[i][1] < dp[j][1] + 1:
                dp[i][1] = dp[j][1]+1
print(sum(max(dp, key=lambda x: sum(x))) + 1)

---