[백준/Python] 1965번 상자넣기

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

알고리즘

앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자에 넣을 수 있고, 한 번에 넣을 수 잇는 최대의 상자 개수를 찾는 코드를 구성해야 하므로, 해당 수열에서 가장 길이가 긴 증가하는 수열을 찾으면 된다. 

dp배열을 만들고, i번째 원소보다 앞에 있는 원소(0 ~ i-1)들중에 i번째 원소보다 작은 원소의 개수를 카운팅해주어 dp배열에 저장하는 방식으로 구성하였다.

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

해당 문제와 코드가 유사하다.

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))
dp = [1 for _ in range(n)]

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

print(max(dp))