[백준] 1965번. 상자넣기

아이디어

1. 자기보다 제일 최근에 작은 수 +1 해준다 -> 반례 (2 3 1 4 5 6)
2. 자기보다 작은 수중에 최댓값에 +1 해준다 -> 반례 (4 5 1 2 3)
3. 앞에 자기보다 작은 수가 없을 때 1을 해준다 (추가)
   (+ 피드백)
4. 처음부터 박스 수를 1로 초기화해놓으면 불필요한 코드 없애도 됨

시간복잡도

• 이중 for문 : n x n = 1000 x 1000 = 1,000,000

코드

1차

import sys
input = sys.stdin.readline

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

dp[0] = 1

for i in range(1, n):
    # 자신의 앞에 있는 box들을 역순으로 조회한다.
    for j in range(i, -1, -1):
        # 자기보다 작으면 +1하고 break
        if box_list[i] > box_list[j] and dp[i] <= dp[j]:
            dp[i] = dp[j] + 1
        else:
            pass
    # 다 돌았는데도 자신보다 작은게 없으면 1을 줘야한다.
    if dp[i] == 0:
        dp[i] = 1

print(max(dp))

2차 불필요한 코드 제거

import sys
input = sys.stdin.readline

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

for i in range(1, n):
    # 자신의 앞에 있는 box들을 역순으로 조회한다.
    for j in range(i, -1, -1):
        # 자기보다 작으면 +1하고 break
        if box_list[i] > box_list[j] and dp[i] <= dp[j]:
            dp[i] = dp[j] + 1
            
print(max(dp))