[백준_1965] 상자넣기 python

처음에 헷갈려서 한번 틀렸던 부분이

증가하는 상황에서 전 dp에 단순히 1을 더해주면 끝이아닌가,,?

하면서 더 빠른 코드를 작성할 수 있겠다는 기대감에 부풀었었다.

또한 백준이 제공한 테스트코드도,

위와같은 상황에 적절하게 빠지기 쉬운 테스트 코드를 제공했다 

사악하다.

그러나 이전까지의 모든 케이스 중에서 현재보다 작은 상자의

디피 최댓값 + 1을 해줘야 한다.

 

시간복잡도 측면에서

n = 1000인데, 1초라는것은

n^2의 시간복잡도는 허용한다는 뜻이다.

# 입력 속도 개선
import sys
input = sys.stdin.readline

# n 입력
n = int(input())

# box_list 입력
box_list = list(map(int, input().split()))

# dp 설계
dp = [
    0 for _ in range(n)
]

# dp 초기설정
dp[0] = 1

# dp 채워넣기
for i in range(1, n):
    # 최댓값 설정
    M = 0
    # box_list의 0번째부터 현재 인덱스 전까지 돌면서
    for j in range(i):
        # j번째 box의 크기가 i번째 box의 크기보다 작으면서
        # 그때의 dp값이 최댓값보다 크다면
        if box_list[j] < box_list[i] and dp[j] > M:
            # 최댓값 갱신
            M = dp[j]

    # dp[i] 채워넣기
    dp[i] = M + 1

# 출력
print(max(dp))