BOJ 2143번 두 배열의 합

BOJ : https://www.acmicpc.net/problem/2143

github : https://github.com/junho0956/Algorithm/blob/master/2143/2143/%EC%86%8C%EC%8A%A4.cpp

 

정올 2001 고등부1번 문제입니다

 

이 문제는 따로 떨어져 있는 경우도 되는 것이 아닌

'부배열' = 연속된 값들로만 해결해야 하는 문제입니다.

makeA, makeB 함수는 연속된 부분집합의 합을 구하는 함수이고, 범위는 1000이기 때문에 충분히 완탐으로 해결됩니다

 

그후에 이분탐색을 이용해서 경우의 수를 구해주시면 됩니다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> va, vb;
int ans, n, m;
int a[1001];
int b[1001];
 
void makeA(int idx, int len) {
    if (idx + len > n) return;
 
    int sum = 0;
    for (int i = idx; i < idx + len; i++) sum += a[i];
    va.push_back(sum);
    makeA(idx, len + 1);
}
 
void makeB(int idx, int len) {
    if (idx + len > m) return;
 
    int sum = 0;
    for (int i = idx; i < idx + len; i++) sum += b[i];
    vb.push_back(sum);
    makeB(idx, len + 1);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> ans >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> m;
    for (int i = 0; i < m; i++) cin >> b[i];
 
    for (int i = 0; i < n; i++) makeA(i, 1);
    for (int i = 0; i < m; i++) makeB(i, 1);
 
    sort(va.begin(), va.end());
    sort(vb.begin(), vb.end());
 
    long long cnt = 0;
    for (int i = 0; i < va.size(); i++) {
        int res = ans - va[i];
        int l = lower_bound(vb.begin(), vb.end(), res) - vb.begin();
        int u = upper_bound(vb.begin(), vb.end(), res) - vb.begin();
        cnt += u - l;
    }
 
    cout << cnt;
    return 0;
}