알고리즘/백준

1028 부분수열의 합2

아메숑 2019. 3. 9. 20:58

1. 문제



2. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include "pch.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
 
//arr의 모든 부분집합의 합을 list에 넣어줌-> 부분집합의 개수 2^arr의사이즈
void makePre(int arr[], int idx, int end, int sum, vector<int> &list)
{
    if (idx == end) {
        list.push_back(sum);
        return;
    }
    makePre(arr, idx + 1, end, sum, list);
    makePre(arr, idx + 1, end, sum + arr[idx], list);
}
 
int main()
{
    int n, sum;
    scanf("%d %d", &n, &sum);
    int arr[50];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    vector<int> left;
    vector<int> right;
    //arr의 인덱스0부터 n/2까지의 부분집합의 합을 left에 넣음
    makePre(arr, 0, n / 2, 0, left);    
    //arr의 인덱스n/2부터 n/까지의 부분집합의 합을 right에 넣음
    makePre(arr, n / 2, n, 0, right);
 
    //오름차순 정렬
    sort(left.begin(), left.end());
    sort(right.begin(), right.end());
        
    long ans = 0;
    int L = 0;
    int R = right.size()-1;
 
    while (L < left.size() && R >= 0)
    {
        long valL = left[L];
        long valR = right[R];
        //만약 sum이 6이고 left=2,2,4이고 right=5,6,6이면 
        //6을 만드는 경우의수는 2*2=4이다. 이 경우의 수를 ans에 넣어준다.
        if (valL + valR == sum)
        {
            long lc = 0;
            while (L < left.size() && left[L] == valL)
            {
                lc++;
                L++;
            }
            long rc = 0;
            while (R >= 0 && right[R] == valR)
            {
                rc++;
                R--;
            }
            ans += (rc*lc);
        }
        else if (valL + valR > sum) {
            R--;
        }
        else
            L++;
    }
    //부분집합을 만들 때 left,right마다 0값이 들어가므로 
    if (sum == 0)
        ans--;
    printf("%ld", ans);
 
    
}
 
cs


3. 후기

이 문제는 n의 길이가 40까지 주어진다. 그럼 부분집합의 경우의 수는 2^40이고 부분수열의 합1처럼 풀면 시간초과가 난다. 그래서 받은 배열을 2개로 나누어서 경우의 수를 2^20까지 줄일 수 있다. 

arr = {-7,-3,-2,5,8}이라면 배열을 두개로 나누어서 모든 부분집합의 합을 각각의 벡터에 넣고, 정렬한다. 

left = {-10,-7,-3,0}

right = {-2,0,3,5,6,8,11,13}

left는 -10부터 right는 13부터 left와 right를 더하면서 sum을 찾으면 ans를 증가시킨다.