백준 1965번 상자넣기

상자넣기 문제 바로 가기

baekjoon 알고리즘 문제 풀이

문제:
정육면체 모양의 상자가 일렬로 놓여 있다. 상자는 각각 너비(정수)를 가지고 있으며, 어떤 상자 A의 너비가 상자 B보다 작다면 A를 B 안에 넣을 수 있다. 상자들을 가장 많이 넣을 수 있는 최대 개수를 구하시오.
입력
첫째 줄에는 상자의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 상자의 너비를 나타내는 N개의 정수가 주어진다. (1 ≤ 너비 ≤ 1,000)
출력
가장 많은 상자를 넣을 수 있는 최대 개수를 출력한다.

풀이 코드


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

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

print(max(dp))

해결 전략:

dp[i]는 i번째 상자를 마지막으로 넣었을 때 최대 상자 개수를 의미
이전 상자 중 너비가 더 작은 j에 대해 boxs[i] > boxs[j]라면
- dp[i] = max(dp[i], dp[j] + 1)로 갱신
결국 가장 긴 증가 부분 수열(LIS)을 구하는 문제와 동일
dp 리스트에서 가장 큰 값이 최대 상자 수가 된다

Vienna sausage

백준 1965번 상자넣기

상자넣기 문제 바로 가기

baekjoon 알고리즘 문제 풀이