알고리즘 유형 : Meet In The Middle
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/1450
소스 코드(파이썬)
import sys, math
import itertools
input = sys.stdin.readline
# 모든 가능한 부분 수열에 대해 각각의 합을 저장한 리스트 반환
def findSub(arr):
sub = []
for select in range(len(arr)+1):
pool = map(sum, itertools.combinations(arr, select))
for p in pool:
if p <= C:
sub.append(p)
return sub
# B의 원소(item)에 대해, A(arr)에서 이분 탐색하며
# A[idx] + item <= C 인 idx 중에 가장 큰 값을 반환
def getPair(arr, item):
if item > C:
return 0
start = 0
end = len(arr)-1
# start == end일 때를 생각해보면,
# 만약 item이 C보다 크다면
# end가 -1까지 내려가서, start 0을
# 반환하므로 맞고, 구하고자 하는 정답
# 이 있는 곳 또는 바로 오른쪽에 위치한 값
# 에 start와 end가 같이 있을 때,
# 어느 경우든 start나 end가 한 칸 이동하여
# 그 때의 start값이 만족하는 pair 값 개수를
# 잘 의미하므로 성립.
while start <= end:
mid = (start + end) // 2
target = arr[mid] + item
if target <= C:
start = mid + 1
else:
end = mid - 1
return start
N, C = map(int, input().split())
weights = list(map(int, input().split()))
count = 0
div = N//2
w_subA = weights[:div]
w_subB = weights[div:]
subsum_a = findSub(w_subA)
subsum_b = findSub(w_subB)
subsum_a.sort()
for b in subsum_b:
count += getPair(subsum_a, b)
print(count)
풀이 요약
-
이 문제는 냅색으로 풀만한 형태를 띠고 있다. 그러나 메모이제이션 리스트에서, C가 최대 이기 때문에, 행을 하나로 최적화한다고 쳐도, 원소 하나에 int형 4바이트라고치면 최대 40억 바이트, 약 40000 MB 이므로 메모리 초과가 발생한다.
그렇다고 브루트포스로 풀 수도 없다. 무게 배열에 대해 가능한 모든 부분 수열의 합을 구한 다음 그 중에서 C 이하인 원소의 개수를 찾으면 이 또한 O(), 약 10억번 연산해야하므로 TLE가 난다.
이럴 때 시간복잡도를 줄이는 방법으로 Meet In the Middle 알고리즘이 있다.
-
먼저 주어진 무게 배열을 두 개로 나눈다. 적당히 반으로 나누기 위해 N/2 크기로 나누면 된다.
그 후 나눠진 A, B에 대해 각각의 모든 가능한 부분수열의 합들을 구한다.
itertools 모듈을 활용해서 구하되, 물건을 아예 넣지 않는 경우도 카운팅해야하므로 뽑는 개수가 0인 조합(combination)도 고려해야한다.
-
그 후, A를 오름차순 정렬 후 B를 순회하면서 A를 이분탐색하자. 이분 조건은
A[idx] + B의 원소 <= C이고, 반환값은 start이다.반환값 start는 그 때의 B의 원소 값과 매칭되어 C 이하를 만족하는 A의 원소의 개수를 의미하는데, 그 이유를 알아보자.
우리는 이분 탐색을 통해 B의 원소 값과 매칭되는 A의 원소 중에서 최대값. 그 중에서 가장 큰 idx에 위치한 값을 찾을 것이다. 왜냐하면 A는 오름차순 정렬되어있기에, 그 값을 찾으면 그 수보다 왼쪽에 위치한 모든 수들은 당연히도 B와 매칭되어 C 이하가 되기 때문이다.
우선 target < C, target > C인 경우에는 실행문을 작성하기 쉬울 것이다. C보다 작다면 C 이하를 만족하는 target이 더 있을 수 있으니 start = mid + 1이고, target > C일 때는 그 반대의 경우이니 end = mid - 1이다.
이제 start == end 일 때를 생각해보면,
만약 A의 어떤 부분이 6 6 7 이 순서일 때, start가 왼쪽 6, end가 7에 위치해있다고 해보자. 그럼 mid가 가운데 6이니 start가 7로 이동하면 end와 같아질것이다. 그러면 이 때의 start 값이 곧 조건을 만족하는 페어 개수를 의미하게 된다. 그러므로 target == C일 때 start = mid + 1를 해준다.만약에 저 경우에서 start와 end가 가운데 6에 위치해있다고 생각해보자. 이 때 반복문의 조건식이 start < end이라면, 여기서 끝나버리므로 start가 옳은 값이 아니게 된다.
그러므로 while의 조건식이 start <= end이다.
배운 점, 어려웠던 점
- Meet In The Middle 알고리즘을 배웠다.
