백준 1208 - 부분수열의 합 2(C++, 복습)

문제 링크입니다. https://www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

'중간에서 만나기' 방법을 사용하는 문제입니다.

중간에서 만나기에 대해 잘나와있는 설명입니다.

해당 블로그를 참고해주세요 -> https://restudycafe.tistory.com/523

 

문제에서 N의 값은 최대 40입니다.

수는 선택하거나 선택하지 않는 2가지 방법이 있습니다. 그렇다면 모든 경우의 수를 확인해보려면 2^40이 나오게 됩니다.

이는 당연히 시간초과 입니다.

 

이럴 경우, 문제에서 사용하는 방법을 사용하는데, 2가지 범위로 나눠 구하는 것입니다.

범위 A와 B로 나눴을 때, 두 범위에서 구한 값의 합이 S만 되면 됩니다.

반으로 나눴다고 가정한다면 2^20 * 2인 경우로 탐색을 끝낼 수 있습니다. -> 시간초과를 피할 수 있게 되었습니다.

 

저는 map을 사용해서 구간에서의 값이 몇 번 나왔는지를 저장했습니다.

map을 사용한 이유는 S의 값이 음수가 나오기도 하며, 최대 합이 40,000,000이기 때문입니다.

 

A 범위에서 X라는 값이 나왔을 때, B 범위에서는 S-X의 값만 나오면 됩니다. 

따라서, B 범위 탐색했을 때 나오는 값을 구하고 싶은 값인 S에서 빼줍니다. -> 해당 값이 몇 번 나왔는지는 map에 저장돼있습니다.

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#include <map>

using namespace std;

int N, S;
int arr[41];
map<int, int> Sum;
long long ans;

void right_sum(int mid, int sum){
    if(mid == N){
        Sum[sum]++;
        return;
    }
    right_sum(mid+1, sum+arr[mid]); // 다음 값 선택할 경우
    right_sum(mid+1, sum); // 다음 값 선택하지 않는 경우
}

void left_sum(int st, int sum){
    if(st == N/2){
        ans += Sum[S-sum];
        return;
    }
    left_sum(st+1, sum+arr[st]);
    left_sum(st+1, sum);
}

void solve() {
	right_sum(N/2, 0); // 시작 위치, 합
	left_sum(0, 0);
	if(S == 0) cout << ans - 1;
	else cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> S;
	for(int i = 0; i < N; i++) cin >> arr[i];
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요