[백준/1965/파이썬] 상자넣기

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

1965번: 상자넣기

Problem

• 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다.
• 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.
• 상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시

조건

• 파일의 첫 번째 줄은 상자의 개수 n (1 ≤ n ≤ 1000)을 나타낸다. 두 번째 줄에는 각 상자의 크기가 순서대로 주어진다. 상자의 크기는 1,000을 넘지 않는 자연수이다.

SOL

문제를 읽어보니, LIS의 길이를 알아내는 문제이다!

앞의 작은 상자를 뒤의 큰 상자에 넣는데 대소관계가 앞의상자<뒤의 상자 가 성립해야하고, 한번에 넣을 수 있는 최대 상자의 개수를 구해야하므로, 이걸 해석하면 LIS를 구하라는 말이 된다! 

#상자 넣기
# LIS 구하기??
import sys
input= sys.stdin.readline
N=int(input().rstrip())
arr=list(map(int,input().split()))
DP=[1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if arr[j]<arr[i]:
            DP[i] = max(DP[i],DP[j]+1)

print(max(DP))
#print(DP)