[BOJ] 1208 : 부분 수열의 합 2

1208 : 부분 수열의 합 2

풀이

투포인터

와 정말 어려운 문제였다…

원래 부분수열의 합같은 경우에는 인풋이 작아서(20) 모든 조합을 구한 다음에

투포인터로 살펴보면 되는 문제였다.

하지만 이문제는 인풋이 2배크다(40) 그래서 부분수열을 20개, 20개로 나눠서 쪼개준다음에

1개는 큰거->작은거, 나머지 1개는 작은거->큰거 이렇게 해서 투포인터로 살펴본다.

그리고 같은숫자만큼 개수만큼 곱해야되는데 범위가 int범위를 초과해서…

ans랑 ans연산에 쓰이는 tmp1,tmp2는 long long을 써줘야한다.(이부분 맞왜틀 한참했다…ㅠㅠ)

그리고 답이 0인경우에는 조합짤때 공집합(0)이 2개나 들어가기때문에 중복되서 1개를 빼준다.

하 정말 어쩌고2,3..이런문제는 확어려워진다. 그냥 어려워지는게 아니라 예외처리할것은 기하급수적으로 늘어나는것 같다.

하다보면 늘겠지…

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <functional>
using namespace std;

int first[20];
int second[20];
//만들수있는 모든 숫자를 만듬
vector<int> vf;
vector<int> vs;

void go(int *arr,int cnt, int n, int sum,int flag) {
    if (cnt == n) {
        if (flag) {
            vs.push_back(sum); 
        }
        else {
            vf.push_back(sum);
        }
        return;
    }
    
    go(arr, cnt + 1, n, sum + arr[cnt],flag);
    go(arr, cnt + 1, n, sum, flag);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, s;
    cin >> n >> s;
    int sw = 1;

    int fn = 0, sn = 0;
    //2개로 나눠서 입력받음
    for (int i = 0; i < n; i++) {
        if (sw) {
            cin >> first[fn++];
            sw = 0;
        }
        else {
            cin >> second[sn++];
            sw = 1;
        }
    }

    go(first,0,fn,0,0);
    go(second, 0, sn,0,1);
    //정렬함
    sort(vf.begin(), vf.end());
    sort(vs.begin(), vs.end(),greater<int>());

    long long ans = 0;
    int fp = 0, sp = 0;
    int vfs = vf.size();
    int vss = vs.size();
    if (vfs == 0) {
        if (s == vs[0]) {
            ans=1;
        }
        cout << ans;
        return 0;
    }
    if (vss == 0) {
        if (s == vf[0]) {
            ans = 1;
        }
        cout << ans;
        return 0;
    }

    int sum = vf[fp] + vs[sp];
    while (fp < vfs && sp < vss) {
        if (sum == s) {
            long long tmp1 = 1;
            long long tmp2 = 1;
            int num1 = vf[fp];
            int num2 = vs[sp];
            while (fp + 1 < vfs && num1 == vf[fp + 1]) {
                fp++;
                tmp1++;
            }
            while (sp + 1 < vss && num2 == vs[sp + 1]) {
                sp++;
                tmp2++;
            }
            ans += tmp1*tmp2;
            if (fp+1 >= vfs || sp+1 >= vss) {
                break;
            }
            fp++;
            sp++;
            
            sum = vf[fp] + vs[sp];
        }
        //작으면 first를 오른쪽으로(더큰수로 갈아끼움)
        else if (sum < s) {
            sum -= vf[fp];
            fp++;
            if (fp < vfs) {
                sum += vf[fp];
            }
        }
        //크면 second를 오른쪽으로(더작은수로갈아끼움)
        else if (sum > s) {
            sum -= vs[sp];
            sp++;
            if (sp < vss) {
                sum += vs[sp];
            }
        }
    }
    if (s == 0)
        ans--;
    cout << ans;
    return 0;
}

Written on April 9, 2019