[Algorithm] 백준 DP #11053 가장 긴 증가하는 부분 수열

 

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

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

 

 

 

 

 

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
dp = [1] * 10001

for i in range(N):
	for j in range(i):
    	if A[i] > A[j]]:
        	dp[i] = max(dp[i], dp[j]+1)
            
print(max(dp))

 

시간복잡도 : O(n^2)

 

 

🔎 풀이 방법 설명

 

 

 

 

dp[i] : A[i]를 마지막 값으로 가지는 가장 긴 증가하는 수열의 길이

 

이중 for문을 돌면서 A의 값을 비교하며 i번째 값과 그 이전 인덱스의 숫자들의 크기를 비교한다.

 

• i=3 인 경우
  • A[3] > A[j] 라면 dp[3]의 값을 업데이트 시켜준다.
  • 현재 dp[3]의 값과 dp[0]+1, dp[1]+1, dp[2]+1 의 값 중 최댓값을 dp[3]에 넣어준다. (이전까지의 숫자들 중 max를 찾고, +1을 한 값을 넣어준다)