📌 문제 정보

링크: https://www.acmicpc.net/problem/1208

유형: 이분탐색, Meet in the middle

난이도: 골드1

스스로 풀었는가? ❌

💻 작성 코드

import sys
from itertools import combinations

readline = sys.stdin.readline
answer = 0
N, TARGET_SUM = map(int, readline().split())
inputs = list(map(int, readline().split()))
front_half = inputs[:N//2]
back_half = inputs[N//2:]

front_half_sequence = []
back_half_sequence = []

def generate_sequence(arr, IS_REVER_SORT):
    sequence = []
    for i in range(len(arr) + 1):
        combs = combinations(arr, i)
        for comb in combs:
            sequence.append(sum(comb))
        
        if IS_REVER_SORT:
            sequence.sort(reverse=True)
        else:
            sequence.sort()
    
    return sequence, len(sequence)

front_half_sequence, front_half_sequence_len = generate_sequence(front_half, False)
back_half_sequence, back_half_sequence_len = generate_sequence(back_half, True)

answer, front_idx, back_idx = 0, 0, 0
 
while front_idx < front_half_sequence_len and back_idx < back_half_sequence_len:
    front_num = front_half_sequence[front_idx]
    back_num = back_half_sequence[back_idx]
    temp_sum = front_num + back_num

    if temp_sum > TARGET_SUM:
        back_idx += 1
    elif temp_sum < TARGET_SUM:
        front_idx += 1
    else: # sum == TARGET_SUM
        temp_front_idx = front_idx
        temp_back_idx = back_idx
        while temp_front_idx < front_half_sequence_len and front_half_sequence[temp_front_idx] == front_num:
            temp_front_idx += 1
        
        while temp_back_idx < back_half_sequence_len and back_half_sequence[temp_back_idx] == back_num:
            temp_back_idx += 1

        answer += (temp_back_idx - back_idx) * (temp_front_idx - front_idx)
        front_idx = temp_front_idx
        back_idx = temp_back_idx

if TARGET_SUM == 0:
    answer -= 1 # 공집합 제거

print(answer)

🎯 접근 방식

1. 입력 배열을 중앙값을 기준으로 두 개의 배열로 나눈다.
2. 하위 배열에서 가능한 부분합을 계산한 후 정렬된 부분합 리스트를 생성한다.
3. 두 정렬된 리스트를 투 포인터 기법을 사용해 순회하면서 두 리스트의 합이 목표값에 도달하는 경우의 수를 계산한다.
4. 목표값이 0이라면 정답에 공집합이 포함되기 때문에 이를 제외한 결과를 출력한다.

💡 개선사항

1. 부분합을 구하는 함수를 리스트 컴프리헨션을 이용해 한줄로 줄일 수 있다.
2. 투 포인터 대신 이진탐색을 사용한다.

https://c4u-rdav.tistory.com/61 링크를 참고해 풀었다.
배열을 하위의 2개로 나누어 시간복잡도를 줄이는 방법이 인상깊다.
[ktb-algorithm-study] 2주차