[백준/파이썬] 1965번 상자넣기

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

1965번: 상자넣기

가장 기본적인 최장 거리 거리 수열 문제이다. 

O(n^2)의 시간복잡도를 가지기 때문! 해당 알고리즘은 백준에 '가장 긴 증가하는 부분 수열' 시리즈를 풀어보면 좋다

 

현재 위치 기준으로 이전 위치들을 탐색하며 본인보다 작은게 있다면 dp 값을 최대로 업데이트 해주는 방식이다.

import sys
#from collections import deque
#import heapq
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

if __name__ == "__main__":
  n = int(input())
  boxes = list(map(int, input().split()))
  
  dp = [1 for _ in range(n)]

  for i in range(n):
      for j in range(i):
          if boxes[i] > boxes[j]:
              dp[i] = max(dp[i], dp[j]+1)

  print(max(dp))