프로그래밍
백준 1965 상자넣기 - 파이썬 풀이 🦄
Rudi
2021. 3. 28. 12:16
백준 1965 상자넣기 - 파이썬 풀이 🦄
문제
DP를 이용해서 증가하는 최대 길이의 부분수열을 찾는 문제
Keypoints
- N 번째 수가 주어졌을 때까지 MAX{Weight(N)보다 작은 모든 수에 대한 길이}+1 을 찾으면 된다.
- optimal substructure
f(n) = max({f(i)| i in (1, n)}) +1
- overapping subproblems
f(n)
은 한 번만 구하고, 새로운n
이 주어질 때마다 업데이트 된다.
Solution
import sys
N= int(sys.stdin.readline())
lst = list(map(int, sys.stdin.readline().split()))
dp = [0 for i in range(1001)]
dp[lst[0]] = 1
for i in range(1, N):
value = lst[i]
maximum = 0
for j in range(value-1, 0, -1):
if dp[j] > maximum:
maximum = dp[j]
dp[value] = max(dp[value], maximum+1)
print(max(dp))