백준 문제 중 11053번, DP, ‘가장 긴 증가하는 부분수열’

백준 문제 중 11053

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

문제

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

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

풀이

문제의 규칙에 맞는 최대값을 구하기 위해서는 현재의 인덱스에서 만들 수 있는 부분수열의 최대 길이를 인덱스마다 각각 구해야한다.

주어진 수열을 A , A의 각 원소를 A[i]라 하고, A[i]의 값에서의 가질 수 있는 부분수열의 최대길이를 dp[i]라 하자.

A[i]의 값에서 가질 수 있는 부분수열의 최대길이 dp[i]를 구하는 방법은 이렇다.

현재 인덱스 i 이전까지의 값들을 A[0], A[1] … A[i-1] 그리고 이들의 부분수열 길이를 각 dp[0], dp[1], … dp[i-1] 이라하자.

i 이하의 모든 인덱스(j)들 중 A[i]>A[j]를 만족하는 j중 dp[j]가 가장 큰 값에 +1 을 한값과 A[i] 값 하나만을 원소로 가지는 부분수열 즉 dp[i] = 1 중 최대값이 dp[i] 가 된다.

다시 말해 현재 인덱스 i 이전에 존재하는 가장 큰 길이의 부분수열에 A[i]를 추가할 수 있는 조건을 만족하므로 이전까지 가장 큰 길이에 +1을 한 값이 A[i]의 최대 dp[i]가 된다.

n = int(input())

a = list(map(int,input().split()))[:n]

dp = [1]*n

for i in range(n):
    for j in range(i):
        if a[j]<a[i]:
            dp[i]=max(dp[i],dp[j]+1)
           

print(max(dp))

6
10 20 10 30 20 50
[1, 2, 1, 3, 2, 4]