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

이번에 배운 이분탐색 개념으로만 이 문제를 풀어보려 했는데 결국 못 풀었다😢
다른 사람들이 푼 것들을 보니 DP개념도 알아야 풀 수 있는 것 같아 겸사겸사 DP 개념도 공부했다.

DP(동적 프로그래밍)는 Dynamic Programming의 약자로 큰 문제를 작은문제로 나누어 푸는 방식이다.

(이름만 들으면 뭔가 엄청날 것 같은데 그정돈 아닌 것 같다ㅎㅎ 물론 나는 이해하는데 애 좀 많이 먹었다...)

모든 작은 문제를 한 번만 풀어야 해서 작은 문제들의 답을 어딘가에 메모해놓고 보다 큰 문제들을 풀어나갈 때 메모해놓은 작은 문제들의 결과값을 이용한다.

구체적인 설명은 나중에 따로 적어야겠당

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력

풀이

메모할 배열을 새로 만들어 받은 값들의 크기를 하나씩 비교하여 메모 배열을 갱신해주고 메모 배열의 크기를 출력해준다. 아래는 메모 배열 역할이다.

 if 받은 값이 메모 배열 내 최고값보다 크면 		
	append해주고
elif 작으면 
	이분탐색으로 메모 배열 탐색
   	if 받은 값과 같은 값을 가진 인덱스가 있으면:
       		그 인덱스에 저장
     	elif 받은 값과 같은 값이 없으면:
       		받은 값보다 작은 값중 가장 큰값 옆 인덱스에 저장

코드

n = int(input())
boxes = list(map(int,input().split()))
dp = [boxes[0]]
def lowerBound(lst, key):
	start ,end = 0,len(lst) -1
	while start < end:
		mid = (start + end) // 2
        	if key <= lst[mid]:
			end = mid
		elif lst[mid] < key:
			start = mid + 1
	return end


for i in range(1,n):
    if dp[-1]<boxes[i]:
        dp.append(boxes[i])
    elif dp[-1] > boxes[i]:
        idx = lowerBound(dp,boxes[i])
        dp[idx] = boxes[i]

print(len(dp))