[C++] 1208번 부분수열의 합 2 - 중간에서 만나기

#include <iostream>
#include <algorithm>
#include <map>

#define LOOP(i, N) for(int i=1; i<=N; i++)
#define MAX_CNT 42

using namespace std;
typedef long long int lld;

int N, S;  //정수의 개수 N, 정수의 합 S
int num[MAX_CNT];  //1~N까지의 숫자
map<int, int> sub_sum;  //부분수열의 합
int boun;  //경계: boundary
lld cnt;

void leftSum(int left, int sum)  //왼쪽 부분수열의 합
{
    if(left==boun) {
        sub_sum[sum]++;
        return;
    }
    leftSum(left+1, sum);
    leftSum(left+1, sum+num[left]);
}

void rightSum(int left, int sum)  //오른쪽 부분수열의 합
{
    if(left==N+1) {
        cnt+=sub_sum[S-sum];
        return;
    }
    rightSum(left+1, sum);
    rightSum(left+1, sum+num[left]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> S; boun=N/2;
    LOOP(i, N) cin >> num[i];
    
    if(N!=1) {
        leftSum(1, 0); rightSum(boun, 0);  //각 부분수열의 합 구하기
        cout << (S ? cnt:cnt-1);  //S가 0일경우 공집합도 있으므로 -1해서 출력 
    }
    else
        cout << (num[1]==S);
    
    return 0;
}

처음에는 이분 탐색이 태그 되어 있길레 왼쪽 부분 수열 찾고 오른쪽 부분 수열 찾아서 정렬한 다음에 이분 탐색으로 찾아야 되는 줄 알았는데 생각해보니까 그냥 map 써서 하면 되는 거였다.

 

map으로 하게 되면 시간이 996?ms 정도 나와서 엄청 느리게 나오는데 그냥 배열 400000개 해서 -는 200000해서 저장하면 엄청 빠르게 시간을 줄일 수 있다. 찾아보니 이런 코드가 있어서 밑에 적었다.

 

 

 

<map 사용 X>

https://www.acmicpc.net/source/25030948

로그인

 

<C++ map>

https://life-with-coding.tistory.com/305

[C++][STL] map 사용법 정리

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.