[BOJ] #1450 냅색문제 (이분 탐색, Python)

🌱 문제

1450번: 냅색문제

 

🌱 풀이

1. 기존 Bruteforce로 풀 수 없는 이유

이 문제는 물건의 개수(n)가 최대 30개 주어집니다. 만약 이 문제를 완전 탐색으로 푼다면 물건 하나하나마다 넣을지 안넣을지 모든 경우를 세면 최대 $2^{30}$번의 연산을 하게 되는데, 이는 10억이 넘는 값으로 무조건 시간 초과가 발생합니다.

기존 Bruteforce로 푼다면 코드가 다음과 같을 것입니다.

import sys
from itertools import combinations
input = sys.stdin.readline

n, c = map(int, input().split())
obj = list(map(int, input().split()))

sum_combination = []
for i in range(0, len(obj) + 1):
    for comb in combinations(obj, i):
        sum_combination.append(sum(comb))

answer = 0
for sum in sum_combination:
    if sum <= c:
        answer +=1
print(answer)

모든 조합을 구한 후, 그 합이 가방에 넣을 수 있는 최대 무게(c)보다 작으면 answer를 1 증가시킵니다. 하지만 이 코드는 무조건 시간초과가 납니다.

 

2. MITM 알고리즘

이 문제는 MITM 알고리즘을 사용해서 풀어야 합니다. MITM 알고리즘은 Bruteforce를 사용하지만 이를 분할해서 연산의 수를 줄이는 알고리즘입니다. Bruteforce 알고리즘을 사용해야 하지만 앞서 말한 것처럼 경우의 수가 클 때 사용할 수 있습니다.

MITM 알고리즘: "2시간 거리에 살던 여자친구를 사귀던 시절, 대부분 데이트를 여자친구 동네 주변에서 했던 기억이 있다. 서로 지쳐서 헤어질 때쯤 만약 여자친구가 중간 지점에서 자주 만나줬더라면 우리 관계가 더 오래갔을까 하는 생각이 문득 들었었다."

n, c = map(int, input().split())
obj = list(map(int, input().split()))
left, right = obj[:n//2], obj[n//2:]
sum_combination_left, sum_combination_right = [], []

for i in range(0, len(left) + 1):
    for sub in combinations(left, i):
        sum_combination_left.append(sum(sub))
sum_combination_left.sort()

for i in range(0, len(right) + 1):
    for sub in combinations(right, i):
        sum_combination_right.append(sum(sub))

• MITM 알고리즘을 사용하려면 먼저 탐색할 자료를 반으로 분할해야 합니다.
• 탐색할 자료(obj)를 반으로 쪼개서, 반으로 쪼갠 리스트에서 조합을 구합니다. 그 조합의 합을 모두 새로운 리스트에 넣어줍니다. (이것만으로도 조합의 개수가 확연히 줄어들 것입니다.)
• 예를 들어 물건의 개수가 4개이고 각각의 무게가 1, 2, 3, 4라면, 전체 조합을 구하면 ${}_4 C {}_0 + {}_4 C {}_1 + {}_4 C {}_2 + {}_4 C {}_3 + {}_4 C {}_4 = 16$개가 될 것입니다. 하지만 절반으로 분할하여 조합을 구하면 (1, 2)의 조합 4개, (2, 3)의 조합 4개로 총 8개 밖에 나오지 않습니다.
  즉, 연산의 횟수가 $O(2^n)$에서 $O(2^{\frac{n}{2}})$으로 줄어들게 됩니다.

 

3. 이진탐색

answer = 0

# 오른쪽 물건 돌면서 왼쪽 물건 가져올 수 있는 경우의 수 합하기
for i in sum_combination_right:
    if i > c:
        continue
    start = 0
    end = len(sum_combination_left)
    while start < end:
        mid = (start + end) // 2
        # 왼쪽 물건과 오른쪽 물건을 더했을 때 c보다 크면
        if sum_combination_left[mid] + i > c:
            end = mid # 왼쪽 물건에서 가져오는 물건의 무게를 줄이기
        else:
            start = mid + 1 # 왼쪽 물건에서 가져오는 물건의 무게 늘리기
    answer += end # end 인덱스의 값이 가져올 수 있는 물건의 경우의 수

• 위에서 반으로 분할할 지료에 대한 모든 조합 경우의 합을 리스트로 만든 후에는 이진탐색으로 가져올 수 있는 조합의 경우를 카운트 합니다.
• 즉, 오른쪽 물건의 경우를 하나 선택했을 때, 왼쪽 물건에서 가져올 수 있는 경우의 개수를 이진탐색으로 찾습니다. 
• 왼쪽 물건에서 이진탐색을 해야 하므로 왼쪽 조합의 합(sum_combination_left)은 정렬을 해주어야 합니다.
• 일반적인 이진 탐색 알고리즘처럼 왼쪽 물건 조합 리스트(sum_combination_left)에서 start, end, mid 인덱스를 설정한 뒤, 왼쪽 물건에서 가져오는 물건들의 조합의 합과 오른쪽 물건들의 조합의 합을 더했을 때, c보다 크면 end를 mid로 줄여서 왼쪽 물건 리스트에서 가져오는 물건의 무게를 줄이고, 그렇지 않으면 왼쪽 물건에서 가져오는 물건의 무게를 늘립니다.
• 이진 탐색이 끝나고 담을 수 있는 최대 무게를 찾으면 end 인덱스의 값이 다져올 수 있는 물건의 경우의 수이므로 answer에 더해줍니다.

 

🌱 코드

# usr/bin/env python
# -*- coding: utf8 -*-
# boj 1450 냅색 문제

import sys
from itertools import combinations
input = sys.stdin.readline

n, c = map(int, input().split())
obj = list(map(int, input().split()))
left, right = obj[:n//2], obj[n//2:]
sum_combination_left, sum_combination_right = [0], [0]

if n == 1 and obj[0] <= c:
    print(2)
    exit()
if n == 1 and obj[0] > c:
    print(1)
    exit()

for i in range(1, len(left) + 1):
    for sub in combinations(left, i):
        sum_combination_left.append(sum(sub))
sum_combination_left.sort()

for i in range(1, len(right) + 1):
    for sub in combinations(right, i):
        sum_combination_right.append(sum(sub))
sum_combination_right.sort()

answer = 0

# 오른쪽 물건 돌면서 왼쪽 물건 가져올 수 있는 경우의 수 합하기
for i in sum_combination_right:
    if i > c:
        continue
    start = 0
    end = len(sum_combination_left)
    while start < end:
        mid = (start + end) // 2
        # 왼쪽 물건과 오른쪽 물건을 더했을 때 c보다 크면
        if sum_combination_left[mid] + i > c:
            end = mid # 왼쪽 물건에서 가져오는 물건의 무게를 줄이기
        else:
            start = mid + 1 # 왼쪽 물건에서 가져오는 물건의 무게 늘리기
    answer += end # end 인덱스의 값이 가져올 수 있는 물건의 경우의 수

print(answer)

 

+) 참고

[알고리즘 기법] Meet In The Middle