[백준 2143] 두 배열의 합 [C]

백준 - 2143

---

풀이

A와 B의 부 배열에 대한 누적 합을 계산 후 정렬해주고,  upper/lower bound로 가능한 경우를 계산해주면 된다.

단, 가능한 경우가 없을 수 있으니 left <= right까지 탐색을 해주어 계산을 하면된다.

---

소스코드

#include <stdio.h>
#include <stdlib.h>
#define MAX 500500
int a[MAX], b[MAX];
int compare(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}
int main(){
    int T, n, m, A[1000], B[1000];
    scanf("%d %d", &T, &n);
    for (int i = 0; i < n; i++) scanf("%d", &A[i]);
    scanf("%d", &m);
    for (int i = 0; i < m; i++) scanf("%d", &B[i]);
	
    int a_len = 0, b_len = 0;
    for (int i = 0, sum = 0; i < n; i++){
        a[a_len++] = (sum = A[i]);
        for (int j = i+1; j < n; j++)
            a[a_len++] = (sum += A[j]);
    }
    qsort(a, a_len, sizeof(int), compare);
	
    for (int i = 0, sum = 0; i < m; i++){
        b[b_len++] = (sum = B[i]);
        for (int j = i+1; j < m; j++)
            b[b_len++] = (sum += B[j]);
    }
    qsort(b, b_len, sizeof(int), compare);
	
    long long cnt = 0;
    for (int i = 0; i < a_len; i++){
        int left = 0, right = b_len-1, mid;
        int diff = T - a[i];
		
        while (left <= right){
            mid = (left+right) / 2;
            if (b[mid] > diff) right = mid - 1;
            else left = mid + 1;
        }
        cnt += right;
		
        left = 0;
        do{
            if (b[mid] >= diff) right = mid - 1;
            else left = mid + 1;
            mid = (left+right) / 2;
        }while (left <= right);
        cnt -= right;
    }
    printf("%lld", cnt);
}

---

출처

2143번: 두 배열의 합