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

문제

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

50641

26004

20342

50.922%

문제

수열 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

풀이

가장 긴 증가하는 부분수열의 응용 문제이다. 

 

원리는 가장 긴 증가하는 부분수열 dp 배열을 하나 만든 후, 

각 인덱스에서부터 가장 긴 감소하는 부분수열의 갯수를 합한 값이 정답이다. 

 

그러므로 두번째 dp 배열은 뒤에서부터 계산하는 가장 긴 감소하는 부분수열의 배열을 만들면 된다.

 

먼저 가장 긴 증가하는 부분수열의 dp 를 하나 (변수명 asc) 로 만든 후, 

가장 긴 감소하는 부분수열의 dp 를 뒤에서부터 계산하는 dp (변수명 desc) 로 만든다. 

 

desc 배열이 0 으로 채워진 이유는 예제처럼 5 까지 올라갔다면, 그 뒤 [2,1] 은 6, 7 로 1 씩 증가하므로, 

asc, desc 배열의 각 요소의 합을 했을 때 1 을 빼주어야 하기 때문이다. 

그리고 desc 배열의 dp 는 뒤에서부터 채워야하기 때문에 nums 배열과 desc 배열을 각각 reverse() 해주었다. 

 

그 후 두 배열의 합 중 가장 큰 값을 출력하면 

끝. 

 

n = int(input())
nums = list(map(int, input().split()))

asc = [1] * n
desc = [0] * n

for i in range(1,n):
	for j in range(0,i):
		left = nums[j]
		right = nums[i]
		if left < right:
			asc[i] = max(asc[i], asc[j] + 1)

nums.reverse()
for i in range(1,n):
	for j in range(0,i):
		left = nums[j]
		right = nums[i]
		if left < right:
			desc[i] = max(desc[i], desc[j] + 1)
desc.reverse()
sum_array = [x + y for x, y in zip(asc, desc)]

print(max(sum_array))