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

문제

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

1965번: 상자넣기

---

문제 요약

정육면체 상자 n개가 일렬로 늘어서 있다.

 

앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수 있다.

 

상자를 넣을 수 있는 방법 중, 한 번에 넣을 수 있는 최대 상자 개수를 출력한다.

---

코드

n = int(input())

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

dp = [1] * n
# dp[i]는 i까지 한 번에 넣을 수 있는 최대 상자 개수

for i in range(1, n): # dp[i]를 갱신시키기 위해 n번 반복
    for j in range(0, i): # 이전 인덱스를 탐색하며 
        if arr[j] < arr[i]: # 현재 i번째 상자 크기가 j번째 상자 보다 더 크면
            dp[i] = max(dp[i], dp[j] + 1) # dp 갱신

print(max(dp))

---

코드 설명

1. i번째 상자까지 한 번에 넣을 수 있는 최대 상자 개수를 저장하는 메모이제이션 테이블 dp를 생성한다.

+ 앞에 자신보다 작은 상자가 없을 경우 1개이므로 초기 값을 1로 설정한다.

 

2. 0번째 상자부터 n-1번째 상자까지 앞 상자의 크기를 비교하며 dp값을 갱신한다.

+ 앞 상자 dp값에 1을 더한 값(앞 상자를 i번째 상자에 넣으므로) 과 현재 dp[i]값을 비교한다.