14003_ 가장 긴 증가하는 수열

https://www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

 

 

 

이전에 dp를 이용해서 for문을 두번 돌리는 방식으로 가장 긴 증가하는 수열을 구했었다. 하지만 위 문제는 같은 시간복잡도를 가지고는 풀 수 없다.

 

 

시간복잡도를 줄이기 위해서 기록을 위한 dp를 두개를 사용할 것이다.

하나는 해당 숫자가 가진 가장 긴증가하는 부분 수열의 길이를 저장할 것이고

하나는 수열을 증가시킬지 이전 수열과 비교할지를 판독하는데 사용할 임시 배열을 사용할 것이다.

 

두번째는 지금은 감이 잘 안잡힐 수 있지만 조금더 자세히 봐보자.

 

10 20 10 30 40 50

 

예제와 같은 위와 같은 수열이 들어온다고 생각해보자.

 

그리고 두개의 dp를 각각

dp = [ 0 0 0 0 0 0 ]

tmp = [ -1000000001 ] 로 두자. tmp엔 들어올수 있는 최솟값보다 작은 수를 하나 두었다.

 

그리고 10, 20, 15, 30 , 40, 50 을 하나씩 넣으면서 수를 비교해 보자.

 

10은 우선 현재 tmp배열보다 크기때문에 tmp에 추가시킬 수 있다.

 

즉 tmp ==>  [ -10000000001 , 10 ] 이 되고 첫 값은 제외하고 수열의 길이는 1이므로

 

dp  ==>  [ 1 0 0 0 0 0 ] 이 될 것이다.

 

20이 들어오면

 

tmp ==> [ -10000000001 , 10 , 20 ]

dp  ==>  [ 1 2 0 0 0 0 ]

 

여기서 15가 들어온다고 생각해보자. 15은 우선 tmp배열에 더 추가될 수는 없다. 그래서 이분탐색을 통해서 tmp 배열중15가 들어갈 수 있는 자리를 찾는다. 

 

15는 10 보단 크고 20보단 작다. 그렇기에 20의 자리에 들어갈 수 있다.

 

즉, 15 가 들어왔을때 최대길이는 2로 고정되고 20대신 15를 넣어버리면 된다.

 

tmp ==> [ -10000000001 , 10 , 15 ]

dp  ==>  [ 1 2 2 0 0 0 ]

 

같은 방식으로 반복해서 tmp와 dp를 찾는다.

 

즉, tmp가 정답 결과랑 같다는 보장은 없다. 그저 값을 반복하고 판단하는 수단일 뿐이다.

 

dp ==> [ 1 2 2 3 4 5 ]

 

위처럼 찾아졌을때 dp를 거꾸로 탐색하면서 5 -> 4 -> 3 -> 2 -> 1 이 되도록 순서대로 값을 출력한다.

 

즉, [ 10 20 15 30 40 50 ] 이므로

 

50 40 30 15 10 이 출력되게 된다. 15를 출력하면서 1을 찾도록 되어있기 때문에 10은 나오지 않는다.

이를 뒤집어서 출력하면 답이 된다.

 

from bisect import bisect_left
n = int(input())
lst = [0] + list(map(int,input().split()))
dp = [ 0 ]* (n+1)
tmp = [ -1000000001 ]
cnt = 0

for i in range(1,n+1):
    if tmp[-1] < lst[i]:
        tmp.append(lst[i])
        dp[i] = len(tmp) -1
        cnt = dp[i]
    else:
        dp[i] = bisect_left(tmp,lst[i])
        tmp[dp[i]] = lst[i]
print(cnt)
print(dp)
print(tmp)
result = []
for i in range(n,0,-1):
    if dp[i] == cnt:
        result.append(lst[i])
        cnt -= 1
result.reverse()
print(*result)