백준 - 가장 긴 증가하는 부분 수열5(14003) 본문
시리즈가 꽤 많은 문제다
이게 푼 지 좀 오래돼서 기억이 가물가물하다.
LIS가 DP로 푸는 방법이 있는데
이 문제는 메모리 제한이 걸리므로
이분탐색으로 풀어주어야 한다.
이분 탐색으로 LIS 길이를 구할 수 있다.
하지만 문제에서는 LIS 요소까지 출력을 해주어야 한다.
나는 이분탐색으로 도출한 최장 길이 값을 이용해서
LIS를 역순으로 탐색해서 값을 저장해 주었다.
def bs_func(target):
l,r=0,len(bs)
t = 0
while l <= r:
mid = (l+r)//2
if bs[mid] < target:
l = mid+1
else:
r = mid-1
t = mid
return t
n = int(input())
data = list(map(int, input().split()))
lis = [0]*n
lis[0] = 1
bs = [data[0]]
for i in range(1,n):
if bs[-1] < data[i]:
bs.append(data[i])
lis[i] = len(bs)
else:
idx = bs_func(data[i])
bs[idx] = data[i]
lis[i] = idx+1
max_count = len(bs)
answer_list = []
for i in range(n-1,-1,-1):
if lis[i] == max_count:
answer_list.append(data[i])
max_count -= 1
print(len(bs))
for i in answer_list[::-1]:
print(i,end=" ")
'알고리즘' 카테고리의 다른 글
백준 - 전깃줄 - 2(2568) (0) | 2023.12.12 |
---|---|
백준 - 멀티탭 스케줄링(1700) (0) | 2023.12.12 |
백준 - 선분 그룹(2162) (0) | 2023.12.12 |
백준 - 롤러코스터(2873) (1) | 2023.12.12 |
백준 - 여러분의 다리가 되어 드리겠습니다!(17352) (1) | 2023.12.10 |
Comments