[백준] 1965번:상자넣기 (python 파이썬)

문제

www.acmicpc.net/problem/1965

1965번: 상자넣기

 

풀이 및 소스코드

입력 받은 박스 크기들을 순서대로 비교해나가서 dp에 저장해주면 된다.

인덱스 i에 대해 보고 있다면,

0부터 i-1번째 까지 박스 크기와 dp값들을 비교한다.

box[i]보다 크기가 작고 dp 값이 최대라면 dp[i] 에 +1 해서 더해준다.

작은 박스가 없다면 1을 대입해주면 된다.

import sys
input = sys.stdin.readline

n = int(input())
box = list(map(int, input().split()))
dp = [0]*n
dp[0] = 1

for i in range(1, n):
    max_size = dp[i] 
    index = i #box[i]보다 작은 크기의 상자가 있었는지 체크하는 변수
    for j in range(i):
        if box[j]<box[i] and max_size<dp[j]: #box[i]보다 작으면서 dp 값이 제일 큰 인덱스를 찾으려는 for문
            max_size = dp[j]
            index = j #작은 크기의 상자가 있었기때문에 index 값은 i가 아닌 값으로 바뀐다.
    if index != i: #작은 크기의 상자가 있었으면 그 중 최댓값 + 1
        dp[i] = max_size+1
    else: #작은 크기의 상자가 없었다면 1대입
        dp[i] = 1
print(max(dp))