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

문제 주소 : www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

문제 확인

 

완전 탐색을 하게 되면 시간 초과가 나므로 이를 방지하기 위해 해쉬와 분할을 사용합니다.

dfs의 변형으로 알고리즘만 이해한다면 쉽게 풀 수 있습니다.

 

풀이

 

n은 최대 40, 각 수는 절댓값이 100000을 넘지 않으므로 해쉬의 컨테이너를 4000000개로 설정하고 2000000을 기준으로 음수와 양수를 구분합니다.

백준 알고리즘 분류에 "중간에서 만나기" 가 의미하는 것을 생각해 보면 dfs를 반으로 나누어 중간에서 부분 수열을 합친다고 생각하면 됩니다.

1 ~ n/2 까지의 수열에서 부분 수열을 먼저 계산하고 n/2 + 1 ~ n 까지의 수열에서 부분 수열 계산 시 s값과 맞아떨어지는 수를 찾으면 개수만큼 결과에 더해줍니다.

result += hash[s - val + 2000000]

( = 현재 값이 7이며 s가 10일 시 left에서 구한 3의 개수가 결과에 더해줘야 하므로 hash[10 - 7 + 2000000] => hash[2000003])

 

코드

#include <cstdio>
#define MID 2000000
using namespace std;
int n, s, m, ary[40], hs[4000001];
long long res;
void left(int cur, int val) {
    if (cur != m) {
        left(cur + 1, val);
        left(cur + 1, val + ary[cur]);
    }
    else
        hs[val + MID]++;
}
void right(int cur, int val) {
    if (cur != n) {
        right(cur + 1, val);
        right(cur + 1, val + ary[cur]);
    }
    else if (-2000000 <= s - val && s - val <= 2000000)
        res += hs[s - val + MID];
}
int main() {
    scanf("%d%d", &n, &s);
    m = n >> 1;
    for (int i = 0; i < n; i++)
        scanf("%d", &ary[i]);
    left(0, 0);
    right(m, 0);
    printf("%lld", s ? res : res - 1);
}