알고리즘 공부/백준

(Python)백준 코딩테스트 연습 - 상자넣기(1965)

HRuler 2023. 5. 24. 12:46

1. 문제

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

 

1965번: 상자넣기

정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가

www.acmicpc.net

2. 풀이

import sys
input = sys.stdin.readline

# n : 상자 개수
n = int(input())

# nList : 상자 크기 리스트
nList = list(map(int, input().split()))

# dp : dp 값 리스트
dp = [1 for i in range(n)]
for i in range(1, n):
    for j in range(0, i):
        if nList[i] > nList[j]:
            dp[i] = max(dp[j]+1, dp[i])

print(max(dp))