백준 11053 가장 긴 증가하는 부분 수열

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

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

실버 2이지만 생각보다 오래걸렸다.

 

이 방법으로 푸는 게 아닌거라고는 알고 있지만, 어떻게든 풀어는 보았다.

 

DP인 만큼 일단 기억할 배열을 만든다.

result = [[None] for i in range(N)]

 

그리고 2중 반복문으로 해당 수로 만든 수열과 DP에 기억된 수열 중 최대 값이 본인보다 작은 수열 중에서 길이가 더 긴 수열로 본인 차례의 가장 긴 수열을 만들고, 마지막 결과에서 그 수열 중에서 길이가 가장 긴 수열의 길이를 출력하는 것이다.

 

import sys

N = int(input())

A = list(map(int, sys.stdin.readline().split()))

result = [[None] for i in range(N)]

for i in range(N):
    cur_list = [A[i]]
    for t in range(i):
        if A[i] > A[t]:
            if len(cur_list) < len(result[t]) + 1:
                cur_list = result[t] + [A[i]]
    result[i] = cur_list

result.sort(key= lambda x : len(x))

print(len(result[-1]))