[BOJ_Python] 11053_가장 긴 증가하는 부분 수열

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

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

내가 생각한 풀이

 나는 리스트의 각 지점까지의 증가하는 수열을 직접 만들어서 풀려고 했다. 아래 내 코드를 보면 i번째 이전의 수들을 리스트에 넣으려했다. 그 수가 수열의 마지막 수보다 크면 수열 리스트에 넣어 각 지점까지의 수열의 길이를 다 구하려 했다. 하지만 input 리스트가 1 3 5 100 101 77 78 101이면 마지막 101까지의 증가 수열이 1 3 5 100 101로 되는 반례가 있었다.

import sys

n = int(input())
lst = [0]
lst.extend(list(map(int, sys.stdin.readline().split())))

dp = [0, 1]
for i in range(2, n+1):
    answer = [0]
    for j in range(1, i):
        if answer[-1] < lst[j] < lst[i]:
            answer.append(lst[j])
    answer.append(lst[i])
    dp.append(len(answer)-1)

print(dp)
print(max(dp))

정답 풀이

• 각 지점의 수가 수열의 마지막인 가장 긴 증가 수열의 수열 길이를 구한다.
• i번 째까지의 가장 긴 수열의 길이는 i번 째 수가 i-1번 째 수보다 크면 i-1번 째 수까지의 가장 긴 수열의 길이 중 max에 +1한 값이 된다. 

import sys

n = int(input())
lst = list(map(int, sys.stdin.readline().split()))

dp = [1] * n
for i in range(1, n):
    for j in range(i):
        if lst[j] < lst[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))