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

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

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

문제

• DP 문제

Keypoints

• 넣는 순서가 아닌 값(value)에 대해서, 개수를 추적한다.

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