Codeforces Round #750 (Div. 2)-B. Luntik and Subsequences

문제 설명

루나는 아침 산책을 가다가 길이가 $n$인 배열 $a$를 발견했다. 그는 배열의 모든 원소 총합인 $s$를 계산했다. 루나는 $a$의 부분 수열의 합이 $s - 1$인 경우 이 부분수열을 거의 완벽하다고 정했다.

루나는 배열 $a$의 거의 완벽한 부분 수열의 개수를 알고 싶어졌다. 그러나 집에 올때 까지 풀지 못했고, 우리의 도움이 필요하다!.

수열 $y$에 있는 원소를 지운 결과 수열이 $x$라면 수열 $x$는 수열 $y$의 부분수열이다. 이때 원소는 다 지워도 되고, 하나도 안지워도 된다.

Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 1000)$ 이 주어진다.

각 테스트케이스의 첫번째 줄에는 배열의 길이 $n (1 \le n \le 60)$ 가 주어진다.

각 테스트케이스의 두번째 줄에는 배열 $a$의 원소 $n$개 $a_1, a_2, ..., a_n(0 \le a_i \le 10^9)$ 가 주어진다.

Output
각 테스트케이스마다 배열의 거의 완벽한 부분수열 개수를 출력한다.

Example
input
5
5
1 2 3 4 5
2
1000 1000
2
1 0
5
3 0 2 1 1
5
2 1 0 3 0

output
1
0
2
4
4

문제 접근

사용한 알고리즘: 수학, 조합론
걸린 시간 : 00:05
풀었지만 빨리 못풀어서 아쉬움이 남는 문제이다. 어떻게 푸는지 다 떠올랐는데 답 근처에서 헤매는 이 기분을 다시는 느끼고 싶지 않다. 그래도 최근 contest에서 B번까지는 안정적으로 푸는 것 같아서 기분 좋다. 이전에는 B번도 못푸는게 허다였는데 그래도 조금 실력이 는것같다고 생각하려한다.

거의 완벽한 부분 수열은 배열 전체의 합보다 $1$이 작은 부분 수열을 찾아야 하기 때문에 우리는 $1$의 원소를 찾아야 한다는 것을 일단 알 수 있다. 그런데 여기서 복병이 등장한다. 이 수열에는 $0$도 나올 수 있기 때문에 $1$과 $0$을 어떻게 조합해야 하는지 생각해야 한다.

$0$은 어떤 방식으로 집어도 상관이 없기 때문에 우리가 $0$을 집는 경우의 수는 $2^{zero}$ 이다. 만약 $0$이 3개 있다면 총 8개의 방식이 있다는 이야기이다. 그냥 단순하게 집합의 개수를 샌다고 생각하면 이해하기 쉬울 것이다. 첫번째 원소를 고르거나 안고르거나, 두번째 원소를 고르거나 안고르거나, 세번째 원소를 고르거나 안고르거나.

그렇다면 $1$의 개수는 어떻게 처리할 것인가? $1$은 하나만 선택해야 하기 때문에 $0$을 집는 전체 경우의 수인 $2^{zero}$ 에서 $1$의 개수를 곱하면 된다. 만약 $1$이 2개 있다면 첫번째 $1$을 선택하고 $0$을 집는 경우의 수 더하기 두번째 $1$을 선택하고 $0$을 집는 경우의 수가 결과가 된다. 여기서 $0$이 공집합이면 어떻게 하냐고 생각하는 사람이 있을 수 있는데 $0$을 하나도 안집는다면 그냥 $1$ 하나만 집는 경우가 되기 때문에 당연히 거의 완벽한 수열의 개수에 포함된다.

정답 코드

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        long long one = 0, zero = 0;
        for(int i = 0; i < n; i++){
            int num; cin >> num;
            if(num == 0) zero++;
            if(num == 1) one++;
        }
        cout << (long long) pow(2, zero) * one << "\n";
    }
    return 0;
}