[백준]1208 부분수열의 합2

1.풀이

N이 40이기 때문에 완전탐색으로는 시간초과가 난다.

(N=20일때 문제 1182 부분수열의 합 (sosoeasy.tistory.com/30) )

따라서 N을 반으로 쪼개고 각각(왼쪽절반과 오른쪽 절반)이 가질 수 있는 합을 구해서 경우의 수를 구해준다.

​

(1) 절반을 잘라서 왼쪽숫자들로 만들 수 있는 모든 숫자의 합(leftsum)을 구하고 그 개수(cnt)를 dictionary형태로 저장한다 ( leftDict[leftsum]=cnt )

(2) 오른쪽 절반에서 rightsum을 구하고, leftDict[S-rightsum]이 있으면 해당 숫자만큼을 ans에 더해준다.

(3) 왼쪽의 합 만으로 S를 만드는 경우의 수, 오른쪽의 합 만으로 S를 만드는 경우의 수는 (2)에서 더해지지 않는다.

따라서 왼쪽(or 오른쪽)만으로 S를 만들 수 있는 경우는 따로 더해준다.

​

※ 반씩 나누었을 때 시간을 줄일 수 있는 이유는 각각의 숫자의 의미를 볼 필요 없이 더하기만 하면 되기 때문에 dictionary형태로 저장한 자료를 쓸 수 있어서 이다.

예를 들어 오른쪽 합(rightSum)을 하나 구했을 때 (S-rightSum==leftSum)이 되는 leftSum을 구하기 위해 나올 수 있는 모든 leftSum을 항상 다 구해야 한다.

=> (left경우의수*right경우의수)

하지만 모든 leftSum을 구해놓고 dictinary에 저장하면 leftSum을 매번 구할 필요가 없는 것이다.

=> (left경우의수 + right경우의수)

 

2. 소스코드

from collections import deque
N,S=map(int,input().split())
L=list(map(int,input().split()))
halfSize=N//2
leftDict={}

def dfsLeft():
    stack = deque([[0, 0]])
    ans = 0
    while stack:
        sum, indx = stack.pop()
        if indx == halfSize:
            continue
        # 해당숫자를 선택하지 않는 경우
        stack.append([sum, indx + 1])
        # 해당숫자를 선택하는 경우
        if sum+L[indx] in leftDict:
            leftDict[sum+L[indx]]+=1
        else:
            leftDict[sum+L[indx]]=1
        stack.append([sum + L[indx], indx + 1])

def dfsRight():
    global ans
    stack=deque([[0,halfSize]])
    while stack:
        sum,indx=stack.pop()
        if indx==N:
            continue
        # 해당숫자를 선택하지 않는경우
        stack.append([sum,indx+1])
        # 해당숫자를 선택하는 경우
        temp=sum+L[indx]
        if S-temp in leftDict:
            ans+=leftDict[S-temp]
        if temp==S:  #오른쪽만으로 만들기
            ans+=1
        stack.append([temp,indx+1])

ans=0
dfsLeft()
dfsRight()
if S in leftDict:  #왼쪽만으로 만들기
    ans+=leftDict[S]
print(ans)