[백준] 1965번 상자넣기

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

처음에 문제가 잘 이해가 안되서 구글링을 통해 다른 사람들의 풀이를 참고해서 풀었다.

이중 for문을 사용하여 현재 상자 위치에서 그 앞에 더 작은 상자가 있다면 그 상자를 현재 상자에 넣는 경우와 현재 dp 테이블 값 중 최댓값을 다시 dp 테이블에 넣는 식으로 풀면 된다.

# 1965 : 상자 넣기

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

# dp 테이블 1로 초기화
d = [1] * 1001

for i in range(1, n):
    for j in range(i):
        # 현재 위치에서 더 작은 상자가 있을 시
        if box[j] < box[i]:
            d[i] = max(d[i], d[j] + 1)
            
print(max(d))

Uploaded by Notion2Tistory v1.1.0