백준 1965번 상자 넣기
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 24219 | 11918 | 9949 | 49.897% |
문제
정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.
상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.
[입력]
파일의 첫 번째 줄은 상자의 개수 n (1 ≤ n ≤ 1000)을 나타낸다. 두 번째 줄에는 각 상자의 크기가 순서대로 주어진다. 상자의 크기는 1,000을 넘지 않는 자연수이다.
[출력]
첫째 줄에 한 줄에 넣을 수 있는 최대의 상자 개수를 출력한다.
문제 해석하기
- 우리는 문제에서 상자를 쌓을 수 있는 최대 개수를 구하고 싶다. 상자를 쌓으려면 이전 상자보다 다음 상자가 더 크기만 하면된다.
- dp를 사용하는 목적중에 하나는 ⇒ 현재 상태를 이전 상태를 이용해서 효율적으로 계산하기 위함이다.
- dp[i]를 이용해서 i번째 상자를 마지막으로 쌓는다고 했을때 이전에 상자들을 가지고 크기를 확인하면서 상자를 쌓을 수 있다.
- i는 여기서 마지막으로 선택된 상자를 의미한다. 따라서 j가 i보다 작을 수 밖에 없다.
- 따라서 boxes[i]보다 boxes[j]의 값이 작으면 상자를 쌓을 수 있기 때문에 dp[j]에 +1을 해줄 수 있는 것이다.
n = int(input())
boxes = list(map(int, input().split()))
# n개 만큼 dp 배열을 초기화해준다
dp = [1] * n
# DP로 LIS 계산
for i in range(n):
for j in range(i):
if boxes[j] < boxes[i]: # 상자를 쌓을 수 있는 경우
dp[i] = max(dp[i], dp[j] + 1)
# 정답 출력
print(max(dp))
오늘의 회고
dp를 이용하면서, 코드들이 더 단순해지고 빠르게 해결되는 것을 확인할 수 있었다. dp사용법을 좀 더 자세히 알아보고 싶다는 생각이 들었다.
