[백준] 1208번 부분수열의 합 2 - 파이썬(Python)

문제 (링크)

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

1208번: 부분수열의 합 2

 

나의 풀이

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

n, s = map(int, input().split())
arr = list(map(int, input().split()))

# meet in the middle
arr_1 = arr[:n//2]
arr_2 = arr[n//2:]

subsum_arr_1 = []
subsum_arr_2 = []

for i in range(len(arr_1) + 1):
    # arr_1에서 0 ~ len(arr_1) + 1개만큼 뽑아 만들 수 있는 부분집합의 합을 구한다.
    comb_1 = combinations(arr_1, i)
    for comb in comb_1:
        subsum_arr_1.append(sum(comb))

for i in range(len(arr_2) + 1):
    # arr_2에서 0 ~ len(arr_2) + 1개만큼 뽑아 만들 수 있는 부분집합의 합을 구한다.
    comb_2 = combinations(arr_2, i)
    for comb in comb_2:
        subsum_arr_2.append(sum(comb))

subsum_arr_1.sort()
subsum_arr_2.sort()

left_pointer = 0
right_pointer = len(subsum_arr_2) - 1
ans = 0

while left_pointer < len(subsum_arr_1) and right_pointer >= 0:
    tmp = subsum_arr_1[left_pointer] + subsum_arr_2[right_pointer]

    # 두 포인터가 가르키는 값의 합이 s와 같다면
    if tmp == s:

        # 부분집합의 합이 같은 경우를 예외처리
        same_count_left = 1
        same_count_right = 1

        same_left_idx = left_pointer
        same_right_idx = right_pointer

        left_pointer += 1
        right_pointer -= 1

        while left_pointer < len(subsum_arr_1) and subsum_arr_1[left_pointer] == subsum_arr_1[same_left_idx]:
            same_count_left += 1
            left_pointer += 1
        
        while right_pointer >= 0 and subsum_arr_2[right_pointer] == subsum_arr_2[same_right_idx]:
            same_count_right += 1
            right_pointer -= 1
        
        ans += same_count_left * same_count_right
    
    elif tmp < s:
        left_pointer += 1
    
    else:
        right_pointer -= 1

# 아무것도 뽑지 않는 경우는 고려하지 않으므로, s가 0이라면 해당 경우의 수 1개를 빼준다
if s == 0:
    ans -= 1
    
print(ans)

코드 설명 및 풀이법

이전에 게시했던 부분수열의 합 문제와는 다른 버전이다.

https://seongonion.tistory.com/98

[백준] 1182번 부분수열의 합 - 파이썬(Python)

위의 1182번 문제는 시간제한이 2초이지만, 이번 문제는 시간제한이 1초로, 기존의 방법을 사용해서는 시간초과가 난다.

 

이번 문제를 풀기 위해선 meet in the middle 방식과 투 포인터 방식을 함께 사용해야한다.

 

meet in the middle은 큰 문제를 두 개로 나눈다는 점에서 분할정복 방식과 유사한 것처럼 보이지만, 재귀적으로 Base Case까지 나누지는 않고, 배열을 절반으로 나누어 처리해 연산 횟수를 줄인다.

 

만약 배열을 나누지 않고 그냥 진행한다면, 각 원소의 부분수열의 합을 구하는 과정에서 N이 최대값인 40일 경우 2^40번의 연산이 필요하다.

 

하지만, 이를 반으로 나누면 2^20 + 2^20번으로 줄일 수 있다.

 

위 문제에서 처리해줘야할 중요한 예외처리는 두 가지이다.

 

첫 번째로, 맨 마지막 부분에 적힌 주어진 입력값 s가 0일때는 구했던 정답에서 1을 빼줘야한다는 것이다.

 

테스트케이스에서 확인할 수 있듯, 부분수열을 뽑는데 아무것도 뽑지 않는 경우는 존재하지 않는다.

 

하지만 combinations 함수로 부분수열의 합을 구해 저장하는 과정에서는 어떠한 원소도 뽑지 않는 경우도 포함된다.

 

따라서, 해당 경우의 수 한 가지를 빼준다.

 

두 번째로, 두 부분수열의 합이 s가 되었을 때, 해당 부분수열과 중복되는 경우가 존재하는지 확인하는 것이다.

 

만약 두 개의 부분수열의 합이 [2, 3, 3, 10], [1, 4, 9] 이고, s가 7이라고 가정했을 때,

 

left_pointer가 인덱스 1을 가리키고 right_pointer가 인덱스 1을 가르킨 상황에서 두 원소를 더한 값이 7이라고 경우의 수를 1만 더해주고 포인터를 이동시키게 되면 left_pointer가 인덱스 2를 가르키고 right_pointer가 1을 가르킨 경우의 수를 세주지 못한다.

 

따라서, 해당 경우를 모두 찾아준 후 곱해주면 중복되는 경우의 예외처리도 해줄 수 있다.