BOJ - 1965

백준 문제 링크
상자넣기

❓접근법

1. 초기값 DP = [1] * N으로 설정한다.
   그 이유는 상자를 하나만 선택할 때는 자기 자신 1개 밖에 없기 때문.
2. 리스트가 [1, 6, 2, 5, 7, 3, 5, 6]이 있을 때
   처음 1과 6을 비교했을 때, 6이 1보다 더 크므로
   (DP[6의 인덱스], DP[1의 인덱스] + 1) 중 더 큰 값을
   DP[6의 인덱스]로 지정하면 된다.
   그럼 DP[1] = 2로 변환된다.
3. 위 방법대로 한번 더 해보면,
   2와 1을 비교했을 때, 2가 1보다 더 크므로
   (DP[2의 인덱스], DP[1의 인덱스] + 1) 중 더 큰 값을
   DP[2의 인덱스]로 지정하면 된다.
   그럼 DP[2] = 1로 변환된다.
   2와 6을 비교했을 때, 2가 6보다 작으므로 조건을 만족하지 못한다.
   ( 더 큰 상자가 아니기 때문이다)
4. max(DP)값을 출력하면 끝!

👌🏻코드

N = int(input())

DP = [1] * N


array = list(map(int, input().split()))

for i in range(1, N):
    
    for j in range(i):
        
        if array[i] > array[j]:
            DP[i] = max(DP[i], DP[j] + 1)
            
print(max(DP))