[구름LEVEL] 화학약품

난이도	정답률
★★★	- %

프리미엄 알고리즘 위클리 비타알고 시즌3 1주차

구름EDU - Be Really Excellent!

문제

해결

key point, N이 40으로 완전탐색으로 찾아내기 굉장히 크기 때문에,
크기가 N인 집합을 절반으로 나눠 N/2크기의 집합 2개로 만들어 해결한다.

1. 절반으로 집합을 나눌 때 어떻게 나눠도 상관없지만 나는 (0 ~ N/2 - 1), (N/2 ~ n - 1) 이렇게 입력받은 순서에서 절반으로 나눴다.
2. 그렇게 절반으로 나눈 집합으로 완전탐색을 진행해서 부분집합을 찾았다.
   
   이때, 공집합 0을 포함하여 배열을 구성해두어야 추후 부분집합의 합을 탐색할 때 올바른 답이 나옵니다. 왜냐하면, 부분집합을 구하는 과정에서 이미 화합물인 0을 찾아냈는데, 공집합이 없다면 투포인터로 탐색할 때, 두 포인터가 가르키는 값이 절대로 0이 될 수 없기 때문입니다. 그래서 공집합을 포함한 부분배열을 각각 구성한 뒤 마지막 출력할 때 제외시켜줍니다.
3. 그리고 투포인터를 이용하여 합이 0인 화학물을 찾아낼 텐데, 이때 반드시 정렬을 해주어야 한다.
   
   왜냐하면, 부분집합을 정렬하지 않고 반복문을 이용하여 합을 계산하면 부분집합을 나눠놓은 이유가 사라진다.
   → O(N^2)
   정렬을 해야 투포인터를 이용해서 두 합이 기준점 0보다 클 때 오른쪽 포인터를 -방향으로 움직이고, 기준점인 0보다 작을 때 왼쪽 포인터를 +방향으로 한 칸씩 움직여서 탐색을 해야 효율적인 탐색이 가능하기 때문이다. → O(N)
4. 왼쪽 포인터가 가리키는 값과 오른쪽 포인터가 가리키는 값의 합이 0이라면, 홍현이가 만들 수 있는 화합물로 ans의 값을 증가시켜야 한다. 이때 count라는 함수를 사용했다.
   
   count함수는 배열에 값이 num인 원소가 몇개 있는지 찾는 함수입니다. upper_bound 는 배열에서 num보다 큰 값들 중 최소인 위치를 반환하고, lower_bound는 num보다 작지 않는 값들 중 최소인 위치를 반환합니다.
   즉, (num보다 크면서, num과 가장 가까운 위치 - num이 시작하는 첫 번째 위치) 가 됩니다.
   이는 이미 배열을 정렬했기 때문에 가능한 일이고, num의 개수를 헤아리는데 효율적입니다.
   
   그리고 다시 포인터들을 각각 한 칸씩 옮겨 줍니다.
5. 모든 부분집합에 대한 합을 탐색했다면 마지막 나오는 ans가 정답입니다. 하지만 공집합을 포함하여 계산하였으므로, 공집합을 제외하여 출력해줍니다. → ans - 1

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, arr[45];
vector<int> v[2];
void func(int idx, int end, int sum, int i) {
    if (idx >= end) {
        v[i].push_back(sum);
        return;
    }
    func(idx + 1, end, sum, i);
    func(idx + 1, end, sum + arr[idx], i);
}
 
ll count(vector<int>& t, int num) {
    return upper_bound(t.begin(), t.end(), num) - lower_bound(t.begin(), t.end(), num);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    // 완전탐색
    func(0, n / 2, 0, 0);
    func(n / 2, n, 0, 1);
    // 정렬 - 필수
    sort(v[0].begin(), v[0].end());
    sort(v[1].begin(), v[1].end());
 
    // 투포인터
    vector<int>::iterator l, r;
    l = v[0].begin(), r = v[1].end() - 1;
    ll ans = 0;
    while (l != v[0].end() && r >= v[1].begin()) {
        if (*l + *r == 0) {
            ans += count(v[0], *l) * count(v[1], *r);
            l = upper_bound(v[0].begin(), v[0].end(), *l);
            r = lower_bound(v[1].begin(), v[1].end(), *r - 1);
        }
        else if (*l + *r > 0) {
            if (r == v[1].begin()) break;
            r--;
        }
        else l++;
    }
    // 공집합 제외
    printf("%lld", ans - 1);
    return 0;
}

 

완전탐색을 비트마스크로 풀면...

비타알고 해설에서 발췌

int main() {
    int n, num; scanf("%d", &n);
    vector<int> seq[2], sub[2];
    for (int i = 0; i < n; ++i) {
        scanf("%d", &num);
        // 인덱스가 짝수면 0, 홀수면 1행에 나눠서 입력 받음
        seq[i % 2].push_back(num);
    }
    for (int i = 0; i < 2; ++i) {
        //비트마스크를 이용하여 모든 부분집합 확인
        for (int j = (1 << seq[i].size()); j > 0; --j) {
            int sum = 0;
            for (int k = 0; k < seq[i].size(); ++k)
                if (j & (1 << k)) sum += seq[i][k];
            sub[i].push_back(sum);
        }
        sort(sub[i].begin(), sub[i].end());
    }
    ...

• 입력을 받을 때, 짝수, 홀수 인덱스로 나눠 각각 0 또는 1행에 입력받았다.
• 부분집합을 헤아릴 때 비트연산자를 사용해서 나눠진 배열의 부분집합을 구했다.

 

후기

완전탐색을 해야할 때 크기가 너무 크면 어떻게 해야하는지 도저히 생각이 안나서 해설을 통해서 공부한 문제이다. 다음에 이런문제를 만난다면 꼭 풀 수 있길! 

투포인터개념도 들어는 봤었지만 문제에 적용해보니 신세계였다. 역시 공부할게 너무 많다!