[백준/Python] 11054번 - 가장 긴 바이토닉 부분 수열

 

문제

https://www.acmicpc.net/problem/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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

 

풀이

 

이전에 풀었던 가장 긴 증가하는 수열에서 시간을 줄이기 위해 리스트에 수열을 덮어쓰는 방법을 생각했다.

 

https://codingjj.tistory.com/30

 

 

바이토닉 부분 수열은 증가하는부분과 감소하는 부분으로 이루어져있으며 그 길이를 계산해야하는 문제다.

반대로 말하면 리스트의 길이가 N이고 임의의 index i을 정했을때 index i를 기준으로 왼쪽은 0부터 i 까지 증가하는 수열 중 길이가 가장 긴 수열을 구하면 되고, 오른쪽은 N부터 index i 까지 증가하는 수열 중 길이가 가장 긴 수열을 구하면 된다.

다음과 같이 인덱스 i를 기준으로 최장길이 수열을 두개 구한 다음 두 길이를 더하고 1을 뺀다. (i가 중복 포함되므로 1을 빼주어야 한다.) 이 값이 최대일 때, 가장 긴 바이토닉 부분 수열의 길이가 된다.

 

Code

 

 

def search(k,st,ed,lst,or_lst,or_num_lst): # 최장수열을 덮어쓰는 함수이다.
    mid=(st+ed)//2
    if st>ed:
        or_lst[st]=lst[k]
        or_num_lst[k]=len(or_lst)
        return
    if lst[k]==or_lst[mid]:
        or_num_lst[k]=len(or_lst)
        return
    elif lst[k]>or_lst[mid]:
        search(k,mid+1,ed,lst,or_lst,or_num_lst)
    elif lst[k]<or_lst[mid]:
        search(k, st,mid-1,lst,or_lst,or_num_lst)

def bitonic(k,lst,or_lst,or_num_lst): # 만약 수열의 마지막 값(최대값)보다 더 큰 값이 나타나면
    if lst[k]>or_lst[-1]:             # 최장 수열의 길이가 늘어나므로 새로 추가한다.
        or_lst.append(lst[k])
        or_num_lst[k] = len(or_lst)
    else:                             # 아니라면 최장 수열의 위치를 찾아 중간에 덮어쓰기 한다.
        search(k,0,len(or_lst)-1,lst,or_lst,or_num_lst)

N=int(input())
lst=list(map(int,input().split()))
asc_num_lst=[0]*N
asc_lst=[]
asc_lst.append(lst[0])
asc_num_lst[0] = 1

lst2=lst[::-1]   # 수열을 뒤집어 최장수열을 구한다.
desc_num_lst=[0]*N
desc_lst=[]
desc_lst.append(lst2[0])
desc_num_lst[0] = 1

for i in range(1,N): # 인덱스 0부터 i까지의 최장수열의 길이를 구해 인덱스 i에 길이를 저장 
    bitonic(i,lst,asc_lst,asc_num_lst)
    bitonic(i,lst2,desc_lst,desc_num_lst)
desc_num_lst=desc_num_lst[::-1] # 구한 인덱스별 최장을 뒤집는다.
ans=0
for i in range(N):
    if ans<asc_num_lst[i]+desc_num_lst[i]-1: # 값을 비교해 최장수열의 길이를 찾는다.
        ans=asc_num_lst[i]+desc_num_lst[i]-1
print(ans)

 

---

이전에 최장수열을 푸는 문제를 풀지 않았다면 고민이 조금 필요했을 것 같은 문제였다.

​

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