크기가 1씩 증가하는 가장 긴 증가하는 부분수열의 길이를 구하는 다이나믹 프로그래밍

15966번: 군계일학

 

주어진 배열에서 ai = a1 + (i-1)을 만족하는 부분 수열 a의 길이의 최댓값을 구하는 문제

 

--------------------------------------------------------------------------------------------------------------------------------------------------

 

그런데 가장 긴 증가하는 부분 수열을 찾는거니까 O(N^2)인가?

 

근데 N이 10만인데?

 

그러면 O(N)에 찾을 수 있다는건가?

 

한참 고민했다..

 

갑자기 번뜩이는?아이디어가 떠올랐다

 

먼저 핵심은 ai = a1 + (i-1)을 만족하는 수열은 무엇을 의미하는가?

 

a1 = 1이면 a2 = 2, a3 = 3,....

 

a1 = 2이면 a2 = 3, a3 = 4,...

 

a1 = 3이면 a2 = 4, a3 = 5,....

 

이렇게 1씩 증가하는 수열을 의미한다.

 

dp[i] = 마지막 원소가 i인 부분 수열의 길이의 최댓값

 

dp[i]를 모두 0으로 초기화 해두고, dp[A[0]] = 1로 초기화하면

 

그러면 부분 수열이 1씩 증가하는 수열이므로, 배열 A를 순회하면서.. dp[A[i]] = dp[A[i]-1] + 1이면 된다.

 

이때, A[i]-1이 A에 존재하지 않는다면 dp[A[i]] = 1로 자연스럽게 된다

 

[1,2,3,4,5,6]에서 dp[1] = 1, dp[2] = dp[1] + 1, dp[3] = dp[2] + 1,...

 

근데 만약에 [1,2,4,5]라고 해보자. dp[1] = 1, dp[2] = dp[1] + 1 = 2인데

 

dp[4] = ?

 

dp[3] + 1인데 지금 dp[3] = 0이므로 dp[4] = 1로 맞게 계산된다는 것을 알 수 있다

 

배열 A의 원소는 10^6까지니까 배열 dp의 크기는 10^6으로 초기화해두면 적절

 

n = int(input())

A = list(map(int,input().split()))

dp = [0]*(10**6+1)

dp[A[0]] = 1

for i in range(1,n):
    
    dp[A[i]] = dp[A[i]-1] + 1

print(max(dp))