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

문제

상자의 크기가 입력된 배열이 주어졌을 때, 앞에서부터 작은 상자를 뒤의 큰 상자에 넣는다면 최대 몇 개의 상자를 겹칠 수 있는지 개수를 묻는 문제이다.

< 그림 1 >

풀이

• 왼쪽의 작은 상자를 오른쪽의 큰 상자에 넣는다는 것은 오른쪽으로 이동하면서 오름차순으로 증가하는 상자를 골라야 한다고 말할 수 있다.
• 즉, 상자배열 내에서 가장 긴 증가하는 부분 수열 (LIS) 을 구한다면, 겹칠 수 있는 최대 상자의 개수를 알 수 있다.
  

알고리즘

1. 겹치는 상자의 개수를 담는 dp 를 1로 초기화한다. 
2. 상자의 크기가 담긴 box 배열을 순회한다.
3. 해당 상자의 이전에 있는 상자들과 비교하면서 담을 수 있는 상자라면, 이전 상자에 담기는 상자의 개수(dp[j])에 1을 더한 값과 현재 dp[i]에 담긴 값을 비교하여 더 큰 값을 dp[i]에 담는다.
4. dp에서 가장 큰 값을 출력한다.

Python 코드

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

def lis(box):
    dp = [1] * n 
    for i in range(1,n): 
        for j in range(i): 
            if box[j] < box[i] and dp[i] < dp[j] + 1: 
                    dp[i] = dp[j] + 1
    return max(dp)
    
print(sol(box))

 

[알고리즘 / Python] 가장 긴 증가하는 부분 수열 (LIS)

 

문제 출처

1965번: 상자넣기