[백준 1965번] 상자 넣기 문제풀이 (with Python)

< 문제 >

 

 

 

 

< 입출력 >

 

 

 

< 풀이 >

이전에 풀었던 백준 11722번과 매우 유사한 문제였다.

비슷한 로직으로 뒤의 숫자가 더 크면 dp[ 뒤의 숫자 ] 와 dp[앞의 숫자] + 1 을 비교해서 더 큰 수를 저장했다.

 

 

< 코드 >

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

dp = [1 for _ in range(N)]

for i in range(N):
    for j in range(i+1, N):
        if arr[i] < arr[j]:
            dp[j] = max(dp[i] + 1, dp[j])

print(max(dp))