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

접근

수열 A 0번 요소부터 i - 1번 요소 중 A[i]보다 작은 수만 탐색하면서, 해당 요소가 가지고 있는 dp값 중 최대값을 찾는다. dp[i]에 해당 최대값보다 1 큰 값을 입력해주고 다음 수로 넘어가 계산을 계속한다.

예를 들어

i	0	1	2	3	4	5
A	10	20	10	30	20	50
dp	1

i = 1 을 탐색할 때, A의 0 ~ i - 1 요소 중 A[1] = 20 보다 작은 요소는 [10]이고, 이 요소들 중 dp 값의 최대값은 10이 가진 1이므로 dp[1] 에는 1을 더하여 2를 입력해 준다.

i	0	1	2	3	4	5
A	10	20	10	30	20	50
dp	1	2

i = 2 를 탐색할 때, A의 0 ~ i - 1 요소 중 A[2] = 10 보다 작은 요소는 없으므로 dp[2]에는 1을 입력해 준다.

i	0	1	2	3	4	5
A	10	20	10	30	20	50
dp	1	2	1

i = 3 을 탐색할 때, A의 0 ~ i - 1 요소 중 A[3] = 30 보다 작은 요소는 [10, 20, 10]이고, 이 요소들 중 dp 값의 최대값은 20이 가진 2이므로 dp[3] 에는 1을 더하여 3를 입력해 준다.

dp는 수열의 특정 값이 증가하는 부분 수열의 최대값일 때의 부분 수열의 길이 값이다.

코드

import sys

n = int(sys.stdin.readline())
m = [0] + list(map(int, sys.stdin.readline().split()))
dp = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
    maximum = 0
    for j in range(i):
        if m[j] < m[i]:
            if dp[j] >= maximum:
                maximum = dp[j]
    dp[i] = maximum + 1
print(max(dp))

더 생각해 볼 것?

더 쉽게 설명하는 방법을 찾아보자.