[백준 11053번] 가장 긴 증가하는 부분 수열 (python)

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

기록

(dp 4일차) dp로 푸는 문제인 걸 알면서도 못풀어서 답답했다. 구글링해서 풀었다ㅠ

 

이 문제는 n번째 수를 가장 큰 수로 가지는 부분수열의 길이를 저장하는 dp 배열을 사용하여, dp[n]=dp[n번째 수보다 작으면서 가장 긴 부분수열을 가진 수]+1를 점화식으로 계산한다.

 

아래와 같이 n=3일 경우, 30보다 작으면서 가장 긴 부분수열을 가지는 20의 부분수열 길이에서 1을 더한 수인 3을 dp[3]에 저장한다.

수열	10	20	10	30	20	50
부분수열길이	1	2	1	3

n=4일 경우, 20보다 작으면서 가장 긴 부분수열을 가지는 10의 부분수열 길이에서 1을 더한 수인 2를 dp[4]에 저장한다.

수열	10	20	10	30	20	50
부분수열길이	1	2	1	3	2

n=5일 경우도 마찬가지로, 50보다 작으면서 가장 긴 부분수열을 가지는 30의 부분수열 길이에서 1을 더한 수인 4를 dp[5]에 저장한다.

수열	10	20	10	30	20	50
부분수열길이	1	2	1	3	2	4

 

코드

N = int(input())
seq = list(map(int, input().split()))

dp = [1]*N
for i in range(N):
    for j in range(i):
        if seq[j]<seq[i] and dp[i]<=dp[j]:
            dp[i] = dp[j]+1

print(max(dp))

1. 가장 긴 부분 증가수열을 저장할 dp 배열을 N길이 만큼 1로 초기화하여 생성한다.

2. N까지 반복하면서 수열 처음부터 자신까지 자신보다 작으면서 가장 긴 부분수열을 가진 수를 찾아 1을 더하여 dp에 저장한다.

3. 입력된 수열에서 가장 긴 부분 증가수열의 길이를 출력한다.