[백준] 1965 파이썬

문제

---

• 백준 1965 (실버 2)

백준 1965

상자의 크기가 n개만큼 주어질 때, 상자의 크기가 증가하는 부분 수열중에서 가장 긴 부분 수열의 길이를 구하는 문제였다.

내 코드

---

비슷한 문제를 과거에 dp를 통해서 풀었던 것이 생각나서 바로 dp를 이용해서 구현해보았다.
처음부터 박스의 길이를 탐색하면서 자신을 포함하는 가장 긴 증가하는 부분 수열의 길이를 dp 리스트에 업데이트해주는 방식으로 구현하였다.

import sys
input = sys.stdin.readline

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

for i in range(1, n):
    for j in range(i):
        if box[i] > box[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))