[백준] 1965번 상자넣기

💡문제접근

• 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면 넣으면 되고 크다면 넣지 않으면 되는 간단한 DP문제다.
• 앞에서부터 모든 박스를 다 넣어야 하는 일반적인 그리디 알고리즘 문제가 아니다. 몇 개의 박스를 뽑아서 넣을 때 한 번에 넣을 수 있는 최대의 상자의 개수를 출력하는 것이 이 문제의 핵심이다.

💡코드(메모리 : 30616KB, 시간 : 236ms)

import sys
input = sys.stdin.readline

n = int(input().strip())
box = list(map(int, input().strip().split()))
# 맨 앞에 있는 박스는 무조건 넣을 수 있으므로 1로 초기화
dp = [1] * (n+1)

for i in range(1, n):
    for j in range(i):
        if box[i] > box[j]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

💡소요시간 : 10m