백준 1965 상자넣기 - 파이썬 풀이 🦄

• 백준 1965 상자넣기 - 파이썬 풀이 🦄
  • 문제
  • Keypoints
  • Solution
  • References

백준 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))

References

Problem Link