[Algorithm]Baekjoon 1208 :: 부분수열의 합 2

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

1208번: 부분수열의 합 2

 
 
using namespace std;
 
int n, s;
int arr[42] = { 0 };
int check[5000001] = { 0 };
int maxIndex = 0;
bool isRight = false;
long long answer = 0;
const int offset = 2000000;
 
void dfs(int index, int sum)
{
    if (index == maxIndex)
    {
        if (!isRight)
        {
            ++check[sum + offset];
        }
        else
        {
            answer += check[s - sum + offset];
        }
 
        return;
    }
 
    dfs(index + 1, sum); // 그대로
    dfs(index + 1, sum + arr[index+1]); // 더해서
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> s;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
 
    }
 
    maxIndex = n / 2;
    dfs(0, 0);
 
    isRight = true;
    maxIndex = n;
    dfs(n / 2, 0);
 
    if (s == 0) cout << --answer;
    else cout << answer;
}
 
 
 

 

간만에 풀어보는 골드1문제. '중간에서 만나기'라는 알고리즘을 처음 접하게 된 문제다.

문제자체는 주어진 수열을 통해 특정숫자를 만들 수 있는 부분수열의 개수를 구하라는, 설명자체는 단순한 문제다.

하지만 n값이 최대 40이기때문에 그냥 완전탐색으로풀면 2^40이라서 반드시 시간제한에 걸린다.

 

그래서 사용되어지는게 'Meet in the Middle', 즉 중간에서 만나기다.

주어진 수열을 그냥 왼쪽, 오른쪽 반으로 쪼갠다.

그리고 왼쪽에서 먼저 해당 수열로 만들 수 있는 숫자들을 전부 구한다.

전부 다 구한다음, 오른쪽 수열에서도 마찬가지로 숫자들을 조합할건데, 오른쪽수열에서 숫자를 조합했을 경우 수행하는 로직은 왼쪽과 다르다.

왼쪽수열에선 그냥 카운팅만 해줬고, 오른쪽에선 숫자를 조합한다음에 타겟값 s에서 우측숫자조합값 sum을 뺀 숫자의 카운팅값을 answer에 합연산해준다.

 

글로써서 복잡해보이지, 그냥 왼쪽수열에서 조합한 값 + 오른쪽수열에서 조합한 값 == 타겟값 s  일 경우,왼쪽수열에서 조합한값을 answer에 합연산 시켜준다는거다.

 

추가적으로 주의할 것은, 타겟값s가 0인 경우이다. 0인 경우, 왼쪽 오른쪽의 수열에서 공집합인경우 두개를 더하면 타겟값s인 0이 되버리니까 카운팅 해버린다. 둘 다 공집합인 경우는 문제조건상 없기때문에, 값 1을 제외시켜준다.

 

이 때 조합한 숫자에 대한 카운팅을 map을 써서 체크해도 통과는 된다. 다만, 700ms대 정도 나왔다.

사실 map을 먼저 고려했던 이유는, 숫자들이 음수가 있기 때문이다. 

하지만 해당음수만큼 +해줘서 양수값으로 매핑시켜버리면 그만이다. 물론 그만큼 메모리는 더 써야겠지만, 속도는 어마어마하게 차이난다.

 

map을 썼을땐 대략 700ms정도가 나왔고, 위의코드처럼 offset값으로 2000000을 줘서 배열로하면 12ms가 나왔다.

offset값으로 2000000을 준 이유는, n값은 최대 40인데 왼,오른쪽으로 쪼개기 때문에 각각 최대 20이다.

이후 숫자들이 -100000으로만 20번 들어오면 최저값이 -2000000이기때문에, 0으로 맞추기위해 offset값을 2000000을 준 것이다.