백준-1965-상자 넣기(LIS)

문제

상자 넣기

풀이

1. 문제조건 해석

   대표적인 LIS(최장증가수열) 문제다. LIS 는 DP를 이용하여 해결한다.

2. 알고리즘

   단순 LIS 문제로, $N^2$에 해결 가능하다. $N\log{N}$에 해결하는 방법은 관련 블로그를 참고하자.

3. 코드

n = int(input())
boxes = [int(_) for _ in input().split()]
dp = [1 for _ in range(n)]
# 최장증가수열 문제
# dp[i] : i에서 끝나는 최장증가수열
answer = 1
for i in range(0, n):
    for j in range(0, i):
        if boxes[i] > boxes[j] and dp[i] < dp[j]+1:
            dp[i] = dp[j] + 1
    if dp[i] > answer:
        answer = dp[i]
print(answer)