[python] 백준 1965번 - 상자넣기

1965번: 상자넣기 (acmicpc.net)

1965번: 상자넣기

이 문제 알고리즘 보면 다이나믹 프로그래밍이라 되어있는데

이 문제 유형이 다이나믹 프로그래밍 중에서도

최장증가수열이라고 LIS 유형인가봐용

구글링 해보니까

LIS가 이 문제 그자체인데

증가하는 원소들의 가장 긴 부분집합이래요

[1][LIS : 최장증가수열 알고리즘] - DP 를 이용한 알고리즘 (Longest Increasing Subsequence Algorithm) (tistory.com)

[1][LIS : 최장증가수열 알고리즘] - DP 를 이용한 알고리즘 (Longest Increasing Subsequence Algorithm)

이분 글 참고했슴니당

저분 글 보시면 완죤 자세히 나와있슴니당

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))

dp = [ 1 for _ in range(n)]
for i in range(1,n):
    for j in range(i):
        if arr[j] < arr[i] and dp[j] + 1 > dp[i]:
            dp[i] = dp[j] + 1
print(max(dp))

알고리즘 공부 마니 해야겠어용

잼네요