백준 #1208 부분수열의 합(2)

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

수열 요소 개수 최대 40개

부분수열의 합 개수는 맥스 2^40 까지 갈 수 있기 때문에 정답을 구하는 변수는 long long 자료형을 사용해야한다.

​

브루트포스로 모든 수열을 확인하면 시간초과가 남. O(2^n)

나름 줄여본다고 오름차순 정렬하고, sum 이 S 보다 커지면 break 하는 수를 써보긴 했는데

[0,0,0,0, ... ,0] , N=0, S=0 인 TC의 경우 사실 의미가 없다. 2^40 다 돌아아한다.

​

근데 이걸 절반 쪼개서 풀면... 된다..? O(2^(n/2) * 2)

​

절반짜리 집합 두 개 각각의 부분수열합을 다 구해보고 적당히 조합하는거라 직관적으로 큰 차이가 느껴지지 않을 수 있는데, 사실상 굉장히 차이가 커진다. 2^(x*2) 와 2^x*2 의 차이!!

​

1. 수열 집합을 절반으로 가른다. 일단 왼쪽 절반의 모든 부분수열의 합을 구하고, 그 합을 key, 갯수를 value로 가지는 map을 만들어서 저장한다.

2. 이제 나머지 절반짜리 집합의 모든 부분수열의 합을 구한다. 부분수열의 합마다 S-sum을 map에서 찾아서 그 value 들을 다 더해주면 답을 찾을 수 있다!