BOJ - 상자넣기(1965)

실버2 : 동적계획법 문제이다.

풀이

기본적인 동적계획법 문제이다.

Code

import sys
 
input = sys.stdin.readline
 
n = int(input())
a = [0] + list(map(int, input().split()))
dp = [1 for _ in range(n + 1)]
 
for i in range(1, n + 1):
    for j in range(1, i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + 1)
 
print(max(dp))

Reference

• 백준(1965번) - 상자넣기