1182 부분수열의 합

음음 부분수열이니 구하는 부분이 연결되어 있다는 뜻이고 그럼 투포인터를 쓰면 되겠다 싶었다. 

 

-> 아! 아니었다. 음수, 양수가 있어서 투포인터를 쓰기는 어려웠다. 

 

다음으로 N이 20밖에 안 되니 모든 경우를 다 살펴보면 되지 않을까 싶었다. 

2중 for문으로 부분수열 다 만들어보면 되지 않나?

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int n, s;
int v[25];

int main() {
    scanf("%d %d", &n, &s);
    
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int size = 0;
        for (int j = i; j < n; j++) {
            size += v[j];
            if (size == s)
                ans++;
        }
    }
    
    printf("%d\n", ans);
    
    return 0;
}

뭐가 문제지? 부분수열의 정의가 내가 생각한것과 다른가? 

그런데 N이 너무 작긴 하다. 

 

아.... 부분수열이 연속된게 아니고 그냥 수열의 원소 중 일부란 뜻이었다. 어쩐지

 

그냥 비트마스크 사용해서 모든 경우 다 구해야지

그런데 틀림ㅋㅋㅋㅠ ㅗ 인내심 바닥나서 집 감 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int n, s;
int v[25];

int main() {
    scanf("%d %d", &n, &s);
    
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    
    int ans = 0;
    for (int i = 0; i < (1 << n); i++) {
        int sum = -1;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                printf("%d ", j);
                if (sum == -1)
                    sum = 0;
                sum += v[j];
            }
        }
        printf("\n");
        if (sum == s) {
            ans++;
        }
    }
    
    printf("%d\n", ans);
    
    return 0;
}

 

다시 와서 해결했다. 

틀릴만한 부분이 오버플로우나 시간복잡도라고 생각했는데 오버플로우는 20 * 1000000이라 안 터지고...

시간복잡도는 2^20 * 20이라 1000000 * 20 안 터진다. 

 

북님 도움받아서 해결했다. 알고보니 sum이 -1이라 문제였다. 숫자가 음수가 나올 수 있어서 sum이 -1이 되는 경우가 있는데 이 때 틀린다. i = 1부터 시작하는걸로 해결했다. 야호~!