[BOJ] 11055 가장 큰 증가하는 부분 수열

 

 

 

문제 조건이 상당히 유했어서, 이런 방식의 접근으로서도 괜찮았던 것 같다.

 

수열 갯수가 1000개로 제한이 되어있었기 때문에, O(n^2) 정도의 시간복잡도로도 풀렸다.

 

실제로 이 경우에는 총 연산횟수가 n(n-1)/2회가 되겠다.

N = int(input())
A = list(map(int,input().split()))
dp = [0 for _ in range (0,N)]
dp[0] = A[0]
answer = 0
for i in range (1,N):
    dp[i] = A[i]
    for j in range (0,i):
        if A[j] < A[i]:
            dp[i] = max(dp[j] + A[i], dp[i])
print(max(dp))

 

요즘은 논문이랑 학회 준비에 상당히 바쁜데, 얼른 잘 끝났으면 좋겠다.

 

취직도 그렇고 (._.