boj11053 가장 긴 증가하는 부분수열 (실버2) - DP

문제 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

 

링크 

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

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

 

 

 

---

 

내 풀이

 

" for i ~ n까지 돌면서 기준을 하나 정해서 기준보다 크면 count ++ 하고, 기준을 그 다음으로 넘기면

O(n)으로 끝낼 수 있다. "

n = int(input())
arr = list(map(int, input().split()))
pivot = arr[0]
count = 1

for i in arr:
    if pivot < i:
        pivot = i
        count += 1
        print(pivot)
print(count)

 

위 방법이 틀린 이유:

0 / 100 / 10 / 200 / 20 / 300 / 400 / 500 / 30 / 40 / 50 / 60 에서 정답은 0, 10, 20, 30, 40, 50, 60 총 7이 나와야 한다.

하지만 위 방법대로 푼다면, 0, 100, 200, 300, 400, 500 총 6이 나온다. 따라서 틀린 방법.

 

 

 

동적할당의 메모이제이션(Memoization)

 

점화식

 

이중 반복문 이용해서 O(n^2)

DP 리스트를 만들어서 for i = range(1, n) 의 범위를 돌고 for j = range(0, i) 까지 반복하며

현재 i 보다 작은 j가 있으면 해당 배열값 + 1을 하여 저장한다.

n = int(input())
arr = list(map(int, input().split()))
dp = [1]*n

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

print(max(dp))