[백준/python] 11055 가장 긴 증가하는 수열

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

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

[알고리즘]

이 문제는 주어지는 리스트 크기만큼 dp를 먼저 선언해두고 계속해서 값을 갱신해주는 방식이다. 배열 원소들의 크기를 비교한 뒤, 바로 count를 해주면 되지않나?라고 생각을 했는데 "수열의 길이"를 구하라고 했기 때문에 dp[i]에 계속 누적을 해줘야 하고 누적된 값들 중, 최댓값을 찾아야 하므로 dp[i], dp[j]+1 중 최댓값을 도출해주는 것이다. 또한 max(dp[i], dp[j]+1)는 결국 li[i] 보다 더 작은 위치에 있는 dp 테이블들 중에서 가장 큰 값으로 바꿔준다는 뜻이다. 그래야 가장 긴 수열의 길이를 도출할 수 있으니까..!

[시간복잡도]

크기가 N인 수열을 이중포문을 통해 비교하므로, O(N**2)

[최종코드]

n = int(input())
li = list(map(int, input().split()))
dp = [1 for _ in range(n)]
for i in range(n) : 
    for j in range(i) : 
        # 0부터 i까지니까 앞의 수들 검사 가능..
        if li[i] < li[j] : 
            # 증가하면 갱신
            dp[i] = max(dp[i], dp[j]+1)
            # print(dp)

print(max(dp))