백준 11053 : 가장 긴 증가하는 부분 수열 (Python)

본문 링크

N=int(input())

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

dp=[0]*N

for i in range(N):
    for j in range(i):
        if L[i]>L[j] and dp[i] < dp[j]:
            dp[i]=dp[j]
    dp[i]+=1
print(max(dp))

📌어떻게 접근할 것인가?

다이나믹 프로그래밍 알고리즘 중에 유명한
$LIS : ( Longest Increasing Subsequence )$ 알고리즘 문제이다.

우리가 구하고자 하는 값은 부분 수열중 가장 긴 부분수열을 찾는 문제이다.

이중 반복문을 사용하여서 모든 리스트 값을 탐색한다.
이때 L[i] > L[j] and dp[i] < dp[j] 의 의미는 수열이 증가하면서 이전에 증가했던 횟수보다 큰가? 라는 뜻이다.

예제 입출력을 보았을때

• 입력
  6
  10 20 10 30 20 50
• 출력
  4

$DP$ 배열의 변화는 이런 양상을 띈다.
처음 10 , 20 까지는 증가하지만 다시 감소했을때 10 보다 작거나 같은 인덱스값을 그대로 들고온다.
만약에 증가했다면 이전의 증가한 횟수의 최대값을 적용시키고 1 을 더해준다.

따라서 $max(dp)$ 값은 최장 길이 부분수열이 된다.

이중 반복문으로 탐색하므로 시간복잡도는 $O(N^2)$ 이다.