[백준 1965번] 파이썬 - 상자 넣기

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

1965번: 상자넣기

 

# 조건

- 크기가 있는 상자들이 주어질 때, 앞의 상자가 뒤의 상자보다 크기가 작다면 뒷 상자에 앞의 상자 넣을 수 있다.

- 예) 1 - 6 - 2 - 5- 7의 크기를 가진 상자가 주어질 때, 1- 6 -7 (3개) 또는 1-2-5-7 (4개)의 방법으로 상자를 넣을 수 있다.

- 한 번에 최대 많은 상자를 넣었을 때의 개수를 구하여라.

 

# 접근 방법

• 넣을 수 있는 모든 경우의 수를 구한다면 시간 초과가 날 것 같기 때문에
• 앞의 부분 경우의 수를 기록해두고 계속 사용하자.
• 현재의 박스를 넣었을 때와 기록되어있는 지금 현재 들어갈 수 있는 최대 박스 개수를 비교해준다.
• 예) 1-6-2-5-7의 경우 처음 모든 박스는 1 1 1 1 1
• 이후 크기가 6인 박스에는 1인 박스가 들어갈수 있으므로 +1 = 1 2 1 1 1
• 크기가 2인 박스가 되면 1 2 2 1 1
• 크기 5박스의 경우 1 2 2 3 1이 된다.
• 중요!! 크기 7박스를 넣는 경우 비교 과정
  • 1이 들어있는 6의 박스를 우선 넣는다면 7 박스는 본인 포함 3개의 박스 ( 1 2 2 3 3)
  • 다음 크기 2 박스를 넣는 것과 같은 개수이므로 패스
  • 크기 5 박스의 경우 이미 3개가 들어가있는데 비교하는 방법
  • -> 5박스 + 7박스 본인 vs 현재 7박스에 기록되어있는 최대 수 == 3을 비교

 

또한 DP를 구현하는 방법 중 이분 탐색을 사용하는 방법과 모든 수를 훑어보는 방법이 있어 2가지로 모두 풀어보았다.

시간 효율적으론 이분탐색이 좋지만, 두 코드 모두 '길이'를 구하는 것이기 때문에, 구성하는 수를 볼 수는 없다.

후자의 방법 같은 경우 최댓값의 인덱스 기준으로 다시 수를 가져오면 되지만, 이분 탐색의 경우 그 정도까지는 아직 어려운 것 같다.

 

상황에 맞는 방법을 사용하는 것이 중요한 것 같다!

 

---

1. 모든 수 훑기 - O(N ^ 2)

import sys
input = sys.stdin.readline

# 앞에서부터 작은 상자를 뒤에 더 큰 상자에 넣는다.
# 이 때 한 번에 넣을 수 있는 최대의 상자 개수

N = int(input())

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


# 들어가는 상자 개수 리스트
# 최소 자기 자신이므로 1로 시작
# 이전의 상자보다 크기가 크다면 +1을 해준다.
# +1을 해준 것과 지금 넣을 상자를 넣었을 때 뭐가 더 많이 들어가는지 비교해주는 것이 핵심
boxes = [1] * N

for i in range(N):
    for j in range(i):
        if box[i] > box[j]:
            boxes[i] = max(boxes[i], boxes[j]+1)

print(max(boxes))

 

 

2. 이분 탐색 이용 - O(NLogN)

import bisect  
  
x = int(input())  
arr = list(map(int, input().split()))  
# dp 리스트, 시작은 배열의 0번 인덱스로 시작
dp = [arr[0]]  
  
for i in range(x):  
	# 배열의 제일 마지막 인덱스 = 제일 큰수 보다 크다면 추가.
    if arr[i] > dp[-1]:  
        dp.append(arr[i])  
    else:  
	    # 아니라면 bisect이용하여 들어갈 왼쪽 인덱스 구해주기
	    # 1, 2, 6이 들어가있는데 현재수가 5라면
	    # 6의 인덱스 왼쪽 2를 반환해준다.
	    # 그 다음 dp리스트의 2번인덱스를 교체
	    # 만약, 1, 2, 5, 6 이라면 또한 2번 인덱스를 만들어준다.
	    # 사용조건 = dp리스트가 정렬되어 있어야 함.
        idx = bisect.bisect_left(dp, arr[i])  
        dp[idx] = arr[i]  
  
print(len(dp))

 

이 문제는 DP에서 자주 나오는 최장 길이 수열의 유형으로서 풀이법 또한 거의 동일하다.

잘 모르겠다면 아래 게시글 참고!

2022.09.07 - [ALGORITHM/알고리즘 알아보기] - [Algorithm] 최장 증가수열 (LIS)