[Python] 백준 11053번: 가장 긴 증가하는 부분 수열 풀이

 

소스코드

n = int(input())
A = list(map(int, input().split()))
dp = [1] * n
for i in range(1,n):
    for j in range(i):
        if A[i] > A[j]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

 

DP를 이용하면 나름 쉽게 풀 수 있는 문제이다.

주어진 수열이 있을 때

예) 1 100 2 3 4 200 300 400 500 6

가장 긴 부분 수열을 찾으면 된다.

 이중 for문을 이용해 j는 0~i-1까지 돌면서 A[i] 랑 A[j] 를 비교하는 것이다.

즉, i보다 앞에 있는 수 중에 A[i] 보다 작다면, dp값을 비교한다.

 

만약 지금 i가 200에 있다고 하자.

dp[4] = 1 2 3 4 로 4이다.

j가 4에 있을 때, 200은 4보다 크므로 dp값이 갱신되어 dp[5] = 5가 된다. (1 2 3 4 200)