[Python] 11053번 가장 긴 증가하는 부분 수열

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

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

---

 

22/09/21

 

 

전형적인 유명한 DP문제. 그리고 그렇게 어렵지도 않은 DP문제이다.

---

 

문제 접근 방식:

 

 

DP[i] = A[i]를 마지막 값으로 가지는 가장 긴 부분 수열의 길이라고 정의하자.

 

그러면 O(n^2)의 시간 복잡도로 우리는 이 문제를 해결할 수 있다.

 

DP[i] = A[i] > A[j] (i > j)가 성립되는 인덱스 j에 대해, DP[0]~DP[i-1]까지의 값들 중에서 DP[j]들의 최댓값 + 1로 정의가 될 수 있기 때문이다.

 

이를 토대로 구현하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 11053번 가장 긴 증가하는 부분 수열
# DP
'''
접근 방법:
DP[i] = A[i]를 마지막 값으로 가지는 가장 긴 부분 수열의 길이
'''
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().rstrip().split()))
DP = [1 for _ in range(N)]
for i in range(1, N):
    DP[i] = max([0]+[DP[j] for j in range(i) if A[i] - A[j] > 0]) + 1
print(max(DP))