[BOJ] Python 백준 상자넣기(1965)

https://www.acmicpc.net/problem/1965

 

 

부분 수열 dp 문제와 매우 유사한 문제이다. 제일 긴 부분 수열 문제처럼 dp 테이블에 1씩 더해주면서 값을 늘려주고 최댓값을 찾으면 된다. 하지만, 마지막 본인 수까지 포함해야함으로 마지막에 max값에 +1을 해준다.

import sys
input  = sys.stdin.readline

N = int(input())
s = list(map(int,input().split()))
dp = [0] * N
for i in range(N):
    for j in range(i):
        if s[j] < s[i]:
            dp[i] = max(dp[i], dp[j] + 1)



print(max(dp)+1)

 

회고.

부분 수열문제를 최근에 풀어 바로 풀 수 있었던것 같다. 만약 2개월 지난 후 본다면 풀 수 있을까 의문이다...