BOJ [Gold IV] 가장 긴 바이토닉 부분 수열 - 11054

문제 링크

분류

다이나믹 프로그래밍(dp)

문제 설명

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

10
1 5 2 1 4 3 4 5 2 1

출력

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

7

아이디어

• 자기 기준으로 앞쪽으로는 증가하는 부분 수열 개수, 뒤쪽으로는 감소하는 부분 수열 개수를 각각 구해서 더하면 된다고 생각함

  → d1(증가) d2(감소) 배열을 각각 정의

• 첫 시도

  for i in range(n):
  	for j in range(i):
    		if a[i] > a[j]:
        		d1[i] = max(d1[i], d1[j]+1)
  	for k in range(n-1, i+2, -1):
    		if a[i] > a[k]:
            	d2[i] = max(d2[i], d2[k]+1)

  이런 식으로 하나의 값에 대해서 한 번에 돌리려고 함

  reverse를 매번 할 수 없으니 감소 수열에 대해서는 인덱스를 뒤에서부터 탐색하는 걸로 작성을 해봤는데 이거는 메모이제이션을 활용한 거라고 할 수 없어서 감소 수열이 잘못 구해짐

• 그래서 아예 reverse한 배열을 정의하고, for문을 두 개로 나눠서 각각에서 증가 수열 / 감소 수열 개수를 구해주기로 함

내 코드

n = int(input())
a = list(map(int, input().split()))
b = list(reversed(a))
d1 = [1] * 1001
d2 = [0] * 1001

for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            d1[i] = max(d1[i], d1[j]+1)

for i in range(n):
    for j in range(i):
        if b[i] > b[j]:
            d2[i] = max(d2[i], d2[j]+1)

result = [i + d for i, d in zip(d1, list(reversed(d2[:n])))]
print(max(result))

• d2는 a랑 인덱스가 달라지니까 reverse 다시 해줘야 하고, 대신 배열을 크게 잡아놔서 [:n]까지에 대해서만 reverse 해주려고 reversed(d2[:n])) 로 작성
  
  

다른 사람 코드

• 대부분 이진 탐색으로 푼 것 같아서 따로 이해하고 추가하기!