코딩테스트/이진 탐색
가장 긴 바이토닉 부분 수열
수타.
2023. 10. 7. 16:56
https://www.acmicpc.net/problem/11054
11054번: 가장 긴 바이토닉 부분 수열
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
www.acmicpc.net
문제요약:
수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.
난이도:
골드4
소요시간:
10분
제출횟수:
1회
코딩:
import sys
from bisect import bisect_left
input = sys.stdin.readline
n = int(input())
arr = list(map(int,input().split()))
ans1 = [0]*n
ans2 = [0]*n
def cal(ans_arr):
result = []
for k,i in enumerate(arr):
piv = bisect_left(result,i)
if piv==len(result):
result.append(i)
else:
result[piv] = i
ans_arr[k] = len(result)
cal(ans1)
arr = arr[::-1]
cal(ans2)
print(max([a+b-1 for a,b in zip(ans1,ans2[::-1])]))
LIS(Longest Increasing Subsequence) 최장 증가 순열의 응용 문제 입니다. 바이토닉 부분 수열 이라 함은, 어떤 특정 지점 까지는 증가하고 그 이후로는 감소하는 부분수열중 가장 긴 부분을 뜻 하는데 , 최장 증가 순열의 길이는 bisect함수를 통해 쉽게 구할 수 있고, 이를통해 배열내에서 n번째일때 그중에서 가장긴 최장수열의 길이를 ans1에 뒤집어서 ans2에 기록해줍니다. 이렇게 한뒤 ans2를 다시 뒤집어 준뒤 zip함수를 통해 둘을 합해주면 특정 지점을 기점으로 했을때 의 바이토닉 부분수열의 최대값이 나옵니다. 그러므로 max함수로 그들중 최대값을 뽑고 이때 본인을 중복으로 세기때문에 둘다 1이 기본으로 들어가므로 -1을 해줍니다.