1182번 부분수열의 합1은 주어진 수열의 크기가 최대 20이기 때문에 brute force 방법을 사용하여 존재할 수 있는 모든 부분 수열을 생성한 후 계산해도 O(2N) = 220-1 = 1,048,575 은 시간초과가 되지 않는다.
하지만 1208번 문제는 길이가 2배 늘어났기 때문에 O(2N) = 24 -1 = 0-1 = 1,099,511,627,776 은 1초라는 시간안에 해결될 수 없다.
중간에서 만나기 (meet in the middle)
완전 탐색을 사용하면 시간 초과가 나는 경우 [중간에서 만나기 (meet in the middle)] 방법을 대안으로 생각해낼 수 있다.
- 문제를 절반으로 나눠서 양쪽 절반에 모든 경우를 다 해보는 방법이다.
- 탐색의 크기가 많이 줄어든다.
재귀를 통해 문제를 가장 작은 크기로 쪼갠 후 다시 합치는 분할 정복과는 달리, 중간에서 만나기는 문제를 절반으로만 나눈다는 차이점을 가지고 있다.
문제
풀이 방법
- 수열을 입력받은 후 절반으로 나눈다. (수열을 a1, a2로 분할)
- 각 수열에서 만들 수 있는 모든 부분수열의 조합을 생성하고, 그 부분수열의 합을 새로운 배열에 저장한다. (
sub_sum()함수를 통해 수행하며, 결과적으로 2개의 합 배열 s1, s1가 생성된다) - 두 배열 s1과 s2의 모든 경우를 조합해서 합이 s가 되는 모든 경우의 수를 카운트한다.
- 이 때, s1은 오름차순으로, s2는 내림차순으로 정렬한 뒤, 두 배열을 투 포인터 방법으로 탐색한다.
- 정렬을 통해 동일한 값을 가진 부분수열을 한 번에 카운트할 수 있으며, 이를 곱하여 효율적으로 결과를 구할 수 있습니다.
Q. 왜 s1는 오름차순 정렬을 하고, s2는 내림차순 정렬을 할까?
A. 투 포인터 기법을 통해 효율적으로 합이 s가 되는 경우를 찾기 위해서이다.
- 중복된 합을 한번에 처리: 정렬된 상태에서 동일한 합을 가진 원소들은 연속되게 배치된다. 이를 통해, 동일한 합을 가진 부분수열들을 한 번에 카운트할 수 있어서 시간 복잡도를 줄일 수 있다.
- 효율적인 탐색: 두 배열 중 하나가 오름차순으로 정렬되어 있고, 다른 하나가 내림차순으로 정렬되어 있을 때, 두 배열의 합을 비교하면서 포인터를 조정하면 효율적으로 목표 합 s에 도달할 수 있다.
if s1[p1] + s2[p2] < s :
s1값을 증가시키기 위해 p1 += 1
# 오름차순 s1를 증가시키면 합이 증가하는 효과
elif s1[p1] + s2[p2] > s :
s2값을 감소시키기 위해 p2 += 1
# 내림차순 s2를 증가시키면 합이 감소하는 효과
elif s1[p1] + s2[p2] == s :
cnt += 1
p1 += 1정답 코드
# 중간에서 만나기 - 1208번 - 부분수열의 합2
from itertools import combinations
# 1. 수열을 입력받은 후 절반으로 나눔
m, s = map(int, input().split())
arr = list(map(int, input().split()))
if m == 1:
if arr[0] == s:
print(1)
else:
print(0)
exit()
a1 = arr[:m // 2]
a2 = arr[m // 2:]
# 2. 모든 부분수열의 조합을 생성 -> 그 부분수열의 합을 새로운 배열에 저장
def sub_sum(array):
sums = []
n = len(array)
for i in range(n + 1):
for comb in combinations(array, i):
sums.append(sum(comb))
return sums
s1 = sub_sum(a1)
s2 = sub_sum(a2)
s1.sort()
s2.sort(reverse=True)
# 3. 투포인터 방식으로 모든 경우의 수 구하기
p1, p2, cnt = 0, 0, 0 # 포인터
while p1 < len(s1) and p2 < len(s2):
current_sum = s1[p1] + s2[p2]
if current_sum == s:
c1 = 1 # s1에서 s1[p1]의 개수를 저장하는 변수
c2 = 1 # s2에서 s2[p2]의 개수를 저장하는 변수
p1 += 1
p2 += 1
while p1 < len(s1) and s1[p1] == s1[p1 - 1]:
c1 += 1
p1 += 1
while p2 < len(s2) and s2[p2] == s2[p2 - 1]:
c2 += 1
p2 += 1
cnt += c1 * c2
elif current_sum < s:
p1 += 1
else:
p2 += 1
if s == 0:
cnt -= 1 # 아무것도 선택 안한 경우 제외하기
print(cnt)시간복잡도 (m = n/2)
= 2m + 2m * log 2m + 2m
= 각 수열에서 가능한 모든 부분수열 만들기 + 합이 저장된 수열을 정렬 + 투포인터
= n * 2n/2
