[BOJ/백준] 2143: 두 배열의 합(C++)

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

2143번: 두 배열의 합

[풀이]

 

2632번 피자판매와 비슷한 문제인데 숫자 범위가 커져서 구간합의 개수를 배열에 저장할 수가 없다.

그래서 맵을 사용해서 저장하였다. 그 외에는 2632번과 동일하다.

 

주의할 점은 결과값을 int형에 저장하면 72%에서 오답이 나온다.

T(-1,000,000,000 ≤ T ≤ 1,000,000,000)이고 각 원소의 절댓값이 1000000 이하이기 때문에 합을 구하는

과정은 int형 안에 다 들어오게 된다.

T와 구간합의 범위에만 신경쓰다보니 경우의 수가 int 범위를 넘어갈 수 있다는 것을 놓쳤다.

1<=n<=1000, 1<=n<=1000이므로 최대 1000*1000*1000*1000의 경우의 수가 나올 수 있다.

(가장 간단하게 n,m이 1000, 모든 원소가 0, T가 0인 경우..)

 

경우의수 나오는 문제는 특히 자료형에 주의

#include <cstdio>
#include <map>
 
using namespace std;
int t, n, m, A[1000], B[1000];
long long ret;
int main() {
 
    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]);
    map<long long, long long> aMap;
 
    for (int i = 0; i < n; i++) {
        long long sum = 0;
        for (int j = i; j < n; j++) {
            sum += A[j];
            aMap[sum]++;
        }
    }
 
    for (int i = 0; i < m; i++) {
        long long sum = 0;
        for (int j = i; j < m; j++) {
            sum += B[j];
            ret += aMap[t - sum];
        }
    }
 
    printf("%lld", ret);
}

https://github.com/has2/Algorithm/blob/master/boj/%EC%95%84%EB%AC%B4%EA%B1%B0%EB%82%98/2143.cpp