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

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

DP 문제다.

수열이 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 구하면 되는 문제.

점화식만 구하면 쉽게 풀 수 있는 문제다.

 

처음에는 dp테이블을 2차원으로 만들어서

dp[i][j] = i번째 수로 시작해서 j번째 수로 끝나는 수열에서 증가하는 부분수열의 길이로 저장하려고 했는데

굳이 그럴 필요 없이, dp테이블을 일차원 배열로 만들고, dp[i]는 i번째 수로 끝나는 증가하는 부분 수열의 길이로 정한 후, 다시한번 for문을 돌면서 arr[j] < arr[i]인 경우, 그리고, j에서 i로 넘어갈 때의 부분수열의 길이가 길어지는 경우 부분수열의 길이를 갱신하면 된다.

 

---

# 11053번: 가장 긴 증가하는 부분수열
n = int(input()) # 수열 길이
dp = [1 for _ in range(1001)] # dp테이블 -> dp[i]: i번째 수로 끝나는 증가하는 부분수열의 길이
arr = list(map(int, input().split()))

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

print(max(dp))