[백준/Python] 1965번 : 상자넣기

문제

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

1965번: 상자넣기

 

---

풀이

최대 상자의 개수를 구하려면 다이나믹 프로그래밍을 활용한 최장 증가 부분 순열을 구현하면 된다.
전체 상자의 개수만큼 1로 이루어진 배열 dp를 생성한다.
두 번째 수부터 검사를 시작한다.
자신(i)보다 앞에 있는 수들(j) 중 작은 것이 있다면,
자신(i)의 dp와 해당 수(j)의 위치에 저장된 dp값 + 1을 비교하여 더 큰 값으로 갱신한다.
이중 반복문을 모두 돌면 dp에 저장된 값들 중 최댓값이 정답이 된다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())
li = [*map(int, input().split())]
dp = [1] * n

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

print(max(dp))