[Baekjoon] DP - 1965 상자넣기

문제

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

 

풀이

큰 문제를 작은 문제로 풀 수 있는 DP

d[n]: n 번째 상자일 때, 한 번에 넣을 수 있는 최대의 상자 개수

 

예시

1) 기준 상자일 때,

2) 기준 상자보다 왼쪽에 있는 상자들 중 최대 상자 개수 구하기

3) 본인 상자 추가

 

코드

import sys

n = int(sys.stdin.readline().rstrip())
boxes = list(map(int, sys.stdin.readline().rstrip().split()))
d = [1] * 1000

for i in range(n):
    for j in range(i):
        if boxes[i] > boxes[j]:
            d[i] = max(d[i], d[j] + 1)

print(max(d))