BaekJoon 1450번 : 냅색문제 (G1 39.134%)
해당 문제는 N개의 물건을 가지고 있고, 최대 M만큼의 무게를 넣을 수 있는 가방에 N개의 물건을 가방에 넣는 방법의 수를 구하는 문제이다.
결국 모든 경우의 수를 다 구해야하는 문제이기에 효율적인 알고리즘을 사용해야하는게 포인트이다.
효율적인 시간복잡도
MITM을 사용하지 않았을 때MITIM을 사용하지 않고 이 문제를 해결하려면, 배열의 모든 부분 집합의 합을 계산한 후 'M'이하인 경우를 찾아야 한다. 배열의 길이가 'N'일 경우, 부분 집합의 총 개수는 2^N이 되고 따라서 모든 부분집합을 고려하는 데에 O(2^N)의 시간복잡도가 소요되고 각 부분집합의 합을 계산하는데 N이 추가로 소요되어 대략적인 시간복잡도는 O(N2^N)이 된다.
MITIM을 사용했을 때
MITM 기법을 사용하면, 문제를 두 개의 하위 문제로 분할하여 각각에 대해 가능한 모든 합의 조합을 계산한다. 각 부분 배열의 길이가 대략 N/2이므로 대략적인 시간복잡도는 O(N^(N/2))이 된다.
- 먼저 모든 경우의 수를 구해야하기에 이 때의 시간복잡도를 줄이기 위해 MITM 알고리즘을 사용한다.
- MITM알고리즘을 통해 두 배열을 절반으로 나누어 각 배열의 조합의 경우의 수를 구해준다. 우리가 구해줘야 하는 것은 각 원소들의 합을 구해줘야 하기에 1부터 해당 배열의 길이까지의 각 조합의 합을 list에 넣어준다.
- 각 조합의 합을 정렬해주고 두 정렬된 배열의 합을 확인했을 때 하나도 넣지 않았을 때와 각 배열에서만 골랐을 때의 경우의 수를 구하기 위해 0을 추가해준다.
- a_list배열의 맨 앞의 인덱스를 start포인터로 지정하고 b_list의 마지막 인덱스를 end포인터로 지정한다.
- 만약 end포인터와 s포인터의 합이 M보다 작을 때의 최초의 경우가 start에서 조건을 만족하는 최후의 index가 end라는 것을 뜻하기에 count에 end의 index+1을 한 값을 더해주고 start의 포인터를 오른쪽으로 한 칸 옮겨준다.
- 만약 그렇지 않을 경우 end포인터를 왼쪽으로 옮겨주어 M이하일 때 까지 줄여준다.
Meet In The Middle(MITM)알고리즘 + 투 포인터
from itertools import combinations as cb
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
arr = list(map(int,input().split()))
index = N//2
a = arr[:index]
b = arr[index:]
a_list = [0]
b_list = [0]
for i in range(1,len(a)+1) :
for j in cb(a, i) :
a_list.append(sum(j))
for i in range(1,len(b)+1) :
for j in cb(b, i) :
b_list.append(sum(j))
a_list.sort()
b_list.sort()
count = 0
s = 0
e = len(b_list) - 1
while s != len(a_list) and e >= 0 :
if b_list[e] + a_list[s] <= M :
count += e + 1
s+=1
else :
e-=1
print(count)투포인터를 이용하지 않고 bisect를 이용한 풀이법도 있다.
Meet In The Middle(MITM)알고리즘 + bisect
from itertools import combinations as cb
from bisect import bisect_right
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
arr = list(map(int,input().split()))
index = N//2
a = arr[:index]
b = arr[index:]
a_list = [0]
b_list = [0]
for i in range(1,len(a)+1) :
for j in cb(a, i) :
a_list.append(sum(j))
for i in range(1,len(b)+1) :
for j in cb(b, i) :
b_list.append(sum(j))
a_list.sort()
b_list.sort()
count = 0
for i in a_list :
count += bisect_right(b_list, M-i)
print(count)
owei