[백준알고리즘] 1208번: 부분수열의 합 2 -Python

[백준알고리즘] 1208번: 부분수열의 합 2 -Python

1208번: 부분수열의 합 2 (acmicpc.net)

1208번: 부분수열의 합 2

기존의 풀었던 1182번 부분수열의 합과 요구하는 것은 같다.

아래는 기존에 풀었던 코드다. 물론 이번 문제에서는 절대 통과되지 않는다.

 

import sys
from itertools import combinations

n, s = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

cnt = 0
for r in range(1, n+1):
    cm = combinations(arr, r)
    for c in cm:
        if sum(c) == s:
            cnt += 1

print(cnt)

 

저번문제보다 수의 범위가 훨씬 커졌다. 여기서 최대 40개의 수가 주어질 수 있는데, 부분 수열을 만들 수 있는 모든 조합의 경우의 수는 2^40이다. 하지만 시간은 이전보다 더 줄었고, 이 경우는 당연히 시간초과에 걸리게 된다.

 

이리저리 시도는 해보는데 전혀 갈피를 못 잡고 질문 게시판을 통해서 푸는 방법을 알게 되었다.

 

문제는 n개의 수가 있는 수열을 주게 되는데, 이 수열을 반으로 나누는 것이다. 그렇게되면 최대 20개짜리 수열이 두 개가 생성되는데 각각의 부분 수열의 조합의 경우의 수는 2^20이다. 따라서 반으로 나눈 두개를 모두 확인하는데 2^21의 경우의 수만 확인하면 되는 것이다.

 

우산 반으로 나눈 왼쪽 수열과 오른쪽 수열에서 각자 만들 수 있는 부분 수열의 합을 구해야 한다. 여기서 중복은 생기면 생기는대로 두어야 한다.

예를 들어 [2, 0, -2] 가 한쪽 수열이라면 이 수열에서 만들 수 있는 부분 수열의 합을 원소로 갖는 리스트는 [-2(=-2), -2(=-2+0), 0(= ), 0(=0), 0(=0+2-2), 2(=2), 2(=2+0)]이다. 0(= )는 하나의 원소도 선택하지 않은 경우이다.

 

 

이렇게 왼쪽수열과 오른쪽 수열에서 각각 구한 부분 수열의 합 리스트를 투 포인터 알고리즘을 이용해 S와 같은지 비교하면 된다.

 

다만, 하나는 리스트에 있는 부분수열의 합이 작은 값부터 큰 값으로 인덱싱 해나 가고, 다른 하나는 반대로 합이 큰 값부터 작은 값으로 인덱싱 해야 한다.

 

주의해야 할 점은 S와 같은 경우에는 같은 경우의 수가 얼마나 있는지 구해주어야 한다. 예를 들어 양쪽 부분 수열의 합 리스트에서 현재 A와 B가 인덱싱 되어있고 A + B = S를 만족하는 상황이라 하자. 그러면 A가 있는 리스트에 A와 같은 값이 a개 있고, B가 있는 리스트에 B와 같은 값이 b개 있다면 총 a*b의 경우의 수만큼 A + B = S가 만족하는 것이다.

이 경우를 고려해주어야 다음과 같은 예제가 통과할 수 있다.

3 0
0 0 0
# output : 7

 

하나 더 주의해야 할 점은 S가 0일 때다. 위에서 [2, 0, -2]의 부분 수열의 합 중에 0이 공집합으로 인해 생긴 경우를 봤다. 반으로 나눈 왼쪽과 오른쪽 리스트에서 각각 공집합을 고르면 부분 수열의 길이가 0이 돼버리기 때문에 크기가 양수인 부분 수열이라는 조건을 만족하지 못하기 때문에 1가지 경우를 빼주어야 한다.

 

from itertools import combinations

n, s = map(int, input().split())
arr = list(map(int, input().split()))
left, right = arr[:n//2], arr[n//2:]

l_sum, r_sum = [], []
for i in range(n//2 + 1):
    cm = list(combinations(left, i))
    for c in cm:
        l_sum.append(sum(c))
for i in range(n - n//2 + 1):
    cm = list(combinations(right, i))
    for c in cm:
        r_sum.append(sum(c))
l_sum.sort(); r_sum.sort()

ans = 0
len_ls, len_rs = len(l_sum), len(r_sum)
lp, rp = 0, len_rs-1
while lp < len_ls and rp >= 0:
    tmp = l_sum[lp] + r_sum[rp]

    if tmp == s:
        lsame, rsame = 1, 1

        lt, rt = lp, rp
        lp += 1
        while lp < len_ls and l_sum[lp] == l_sum[lt]:
            lsame += 1
            lp += 1
        rp -= 1
        while rp >= 0 and r_sum[rp] == r_sum[rt]:
            rsame += 1
            rp -= 1
        
        ans += (lsame * rsame)
    elif tmp < s:
        lp += 1
    else: # tmp > s
        rp -= 1

print(ans-1 if s == 0 else ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다