[백준(BOJ)] #1208- 부분수열의 합 2 (파이썬, PyPy3)

문제

 

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

1208번: 부분수열의 합 2

 

---

문제 풀이

2022.08.16 - [PS/백준] - [백준(BOJ)] #1182- 부분수열의 합 (파이썬, PyPy3)

[백준(BOJ)] #1182- 부분수열의 합 (파이썬, PyPy3)

 

이전 글에서 다룬 부분수열의 합 문제와 문제는 같지만 정수의 개수 범위가 다릅니다.

 

부분수열의 합에서는 1 <= N <= 20이었고, 지금 다루는 문제는 1 <= N <= 40입니다.

 

부분수열의 합처럼 모든 부분 수열을 구하기에는 너무 많은 시간이 소요됩니다.

 

경우의 수에 따라 연산을 하기 때문에 1 <= N <= 20일 경우 최대 2^20번(=1,048,576)의 연산이 필요하므로 제한 시간 내에 해결할 수 있지만 1 <= N <= 40의 경우 최대 2^40번(=1,099,511,627,776)의 연산이 필요하므로 시간 초과가 발생합니다.

 

따라서 수열을 반으로 나눈 뒤 각각의 부분 수열에서 합을 구해 리스트를 만들고, 만들어진 두 리스트에서 합이 s인 경우를 찾아 해결했습니다. 이럴 경우 2^20 + 2^20번의 연산으로 해결할 수 있습니다.

 

여기에 적용되는 알고리즘은 Meet in the Middle이라는 알고리즘이고, Meet in the Middle 알고리즘은 분할정복과 비슷해 보이지만, 작은 문제 해결과 더불어 +α의 연산이 필수적이라는 점에서 다릅니다.

 

2022.07.21 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 분할정복(Divide & Conquer)과 병합/퀵정렬

[파이썬으로 배우는 알고리즘] 분할정복(Divide & Conquer)과 병합/퀵정렬

 

1) 위와 같이 수열을 반으로 나누고, 나뉜 수열에서 각각 부분 수열을 구해줍니다.

 

2) 각각의 부분 수열 합의 리스트를 만들어 왼쪽 수열에서 만든 부분 수열의 합 리스트는 오름차순, 오른쪽 수열에서 만든 부분 수열의 합 리스트는 내림차순으로 정렬해줍니다. 이렇게 정렬해준 이유는 두 개의 리스트에서 포인터를 사용해 합이 s인 경우를 찾아나가는데 이를 쉽게 하기 위해서입니다.

 

3) 각 리스트에 0부터 포인터를 설정하여 두 포인터에 위치한 값의 합과 S를 비교하면서 답을 도출합니다.

 

만약 두 개의 포인터가 위치한 값의 합이 s이면 각 포인터에서 위치한 값과 현재 값이 다를 때까지 포인터를 증가시킵니다. (중복 값 고려)

 

ex)
t1 = [-5 ,- 3, -3, -1]
t2 = [10, 10, 10, 3]

수열에서 두 개의 부분 수열 합의 리스트가 주어지고 s = 7, lt = 1, rt = 0일 때

lt는 기존 가리키는 값 -3이 아닐 때까지 증가시키므로 -1의 인덱스인 3까지 증가하고
rt는 기존 가리키는 값 10이 아닐 때까지 증가시키므로 3의 인덱스인 3까지 증가

(3 - 1(기존 lt)) * (3 - 0(기존 rt)) = 6   

부분 수열의 합이 s(=7)가 될 수 있는 경우 = 6

합이 s보다 크면 rt를 1 증가시킵니다. (합의 감소)

 

합이 s보다 작으면 lt를 1 증가시킵니다. (합의 증가)

 

4) s가 0일 경우 두 수열에서 공집합일 때를 더한 값은 답에서 빼줍니다. 

 

---

구현

코드

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

if __name__ == "__main__":
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    
    # 반으로 나누기
    t1 = a[:n//2]
    t2 = a[n//2:]
    
    # 부분 수열의 합 저장하기 위한 리스트
    t1_sum_list = list()
    t2_sum_list = list()
    
    # 왼쪽 수열의 부분 수열 합 저장
    for i in range(len(t1)+1):
        for com in combinations(t1, i):
            t1_sum_list.append(sum(com))
    t1_sum_list.sort()
    t1_len = len(t1_sum_list)
            
    # 오른쪽 수열의 부분 수열 합 저장        
    for i in range(len(t2)+1):
        for com in combinations(t2, i):
            t2_sum_list.append(sum(com))
    t2_sum_list.sort(reverse=True)
    t2_len = len(t2_sum_list)
    
    res = 0
    lt, rt = 0, 0
    while lt < t1_len and rt < t2_len:
        lp, rp = t1_sum_list[lt], t2_sum_list[rt]
        t_sum = lp + rp
        
        # 합이 s와 같은 경우
        if t_sum == s:
            tlt, trt = lt, rt
            # 같은 값이 있는 동안 포인터 증가
            while tlt < t1_len and t1_sum_list[tlt] == lp:
                tlt += 1
            while trt < t2_len and t2_sum_list[trt] == rp:
                trt += 1
            # 중복값이 있을 수도 있으므로
            res += (tlt - lt) * (trt - rt)
            lt, rt = tlt, trt
        # 합이 s보다 큰 경우
        elif t_sum > s:
            rt += 1
        # 합이 s보다 작은 경우
        else:
            lt += 1
    # s가 0인 경우 공집합 제거
    if s == 0:
        print(res-1)
    else:
        print(res)

결과