[2143번] 두 배열의 합

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 부분 합

2. 정렬

3. 투 포인터

이 문제는 메모리가 32MB 밖에 안된다는 점에서 메모리 사용을 통한 시간 단축보다 시간을 적절히 이용하여 메모리를 잘 써야하는 문제이다.

처음에 Map으로 문제를 만들어 부분합이 s이면 map[t-s]가 존재한다면 그 부분합의 수를 가지는 map의 개수를 더해주면 된다고 생각했다.(아래 코드를 올리겠습니다.)

그런데 저렇게 하니 메모리 초과가 떳고, 다른 방법을 생각해야 했다.

물론 Map은 문제 힌트인 투 포인터 개념이 아니었다.

다시 생각해보니 1000개밖에 되지 않기에, 부분합이 최대 1000*999개라서 이중 for문으로 O(100만 * 2) (a,b배열 두개)로 일단 모든 부분합을 구할 수 있었다.

이 두개를 정렬하고, a 부분합 포인터는 시작점 부터, b 부분합 포인터는 끝점 부터 시작하여 

a포인터가 증가하면 총 합이 증가하고 b포인터가 감소하면 총 합이 감소한다는 점을 이용하여 문제를 해결하였다.

PS. 이 문제가 MAP으로 AC를 받을 수 있다고 들었다. 

내 코드와 그 코드의 정확한 차이를 모르겠고, 두 코드의 차이를 아시는 분이 있다면 알려줬으면 좋겠다.

문제를 해결하였다.

if(mp[x] != 0)이라 할 경우 mp[x]가 존재하든 않든 map에 생성을 하게 된다. 

따라서 이 과정에서 메모리를 계속 먹기에 overflow가 났고, 이 과정을 없애기 위해 mp.count(x)를 통해 해결 할 수 있다.

소스 코드 : 

(AC 코드, 투 포인터)

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int a[1001];
int b[1001];
vector<int> vc1;
vector<int> vc2;
 
int main()
{
    int t;
    scanf("%d", &t);
 
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
 
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
        scanf("%d", &b[i]);
 
    for (int i = 0; i < n; i++)
    {
        int sum = a[i];
        vc1.push_back(sum);
        for (int j = i + 1; j < n; j++)
        {
            sum += a[j];
            vc1.push_back(sum);
        }
    }
 
    for (int i = 0; i < m; i++)
    {
        int sum = b[i];
        vc2.push_back(sum);
        for (int j = i + 1; j < m; j++)
        {
            sum += b[j];
            vc2.push_back(sum);
        }
    }
 
    // 두 부분합 벡터를 오름차순 정렬해준다.
    sort(vc1.begin(), vc1.end());
    sort(vc2.begin(), vc2.end());
 
    // p1은 처음부터, p2는 끝부터 시작
    int p1 = 0;
    int p2 = vc2.size() - 1;
    long long int cnt = 0;
 
    while (1)
    {
        // 합이 t와 같은 경우
        if (vc1[p1] + vc2[p2] == t)
        {
            // 합이 될 수 있는 vc1의 현재 부분합과 같은 수의 개수
            // vc2의 현재 부분합과 같은 수의 개수를 서로 곱한다.
            long long int cnt1 = 1;
            long long int cnt2 = 1;
 
            while (p1 + 1 <= vc1.size() - 1 && vc1[p1] == vc1[p1 + 1])
            {
                p1++;
                cnt1++;
            }
 
            while (p2 - 1 >= 0 && vc2[p2] == vc2[p2 - 1])
            {
                p2--;
                cnt2++;
            }
 
            cnt += cnt1 * cnt2;
            p1++; // p2--를 해도 된다.
        }
 
        // 합이 작은 경우 p1++를 통해 합을 크게 해준다.
        if (p1 <= vc1.size() - 1 && p2 >= 0 && vc1[p1] + vc2[p2] < t)
            p1++;
 
        // 합이 큰 경우 p2--를 통해 합을 작게 해준다.
        if (p1 <= vc1.size() - 1 && p2 >= 0 && vc1[p1] + vc2[p2] > t)
            p2--;
 
        // 범위 초과 경우 (존재하지 않는 경우)
        if (p1 > vc1.size() - 1 || p2 < 0)
            break;
    }
 
    printf("%lld", cnt);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

(AC 코드 메모리 초과 코드, Map STL)

#include <stdio.h>
#include <map>
#define MAX 1010
#define LI long long int
 
int suma[MAX], sumb[MAX];
int T;
int n, m;
LI answer;
std::map<int, int> mp;
 
int main(void){
    int a, sum;
    int i, j;
    scanf("%d", &T);
    scanf("%d", &n);
    for (i=1;i<=n;i++){
        scanf("%d", &a);
        suma[i]=suma[i-1]+a;
    }
    scanf("%d", &m);
    for (i=1;i<=m;i++){
        scanf("%d", &a);
        sumb[i]=sumb[i-1]+a;
    }
    for (i=1;i<=n;i++){
        for (j=i;j<=n;j++){
            sum=suma[j]-suma[i-1];
            mp[sum]++;
        }
    }
    for (i=1;i<=m;i++){
        for (j=i;j<=m;j++){
            sum=sumb[j]-sumb[i-1];
            answer+=(LI)mp[T-sum];
        }
    }
    printf("%lld\n", answer);
    return false;
}
 
                                                

(메모리 초과 코드, Map STL)

#include <iostream>
#include <cstdio>
#include <map>
 
using namespace std;
 
int a[1001];
int b[1001];
map<int, short> mp1;
 
int main()
{
    int t;
    scanf("%d", &t);
 
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
 
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
        scanf("%d", &b[i]);
 
    int sum;
    for (int i = 0; i < n; i++)
    {
        sum = a[i];
        mp1[sum]++;
        for (int j = i + 1; j < n; j++)
        {
            sum += a[j];
            mp1[sum]++;
        }
    }
 
    long long cnt = 0;
    for (int i = 0; i < m; i++)
    {
        sum = b[i];
 
        if (mp1[t - sum])
            cnt += mp1[t - sum];
 
        for (int j = i + 1; j < m; j++)
        {
            sum += b[j];
 
            if (mp1[t - sum])
                cnt += mp1[t - sum];
        }
    }
 
    printf("%lld",cnt);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

(메모리 초과 코드를 AC 받은 코드, Map STL)

#include <iostream>
#include <cstdio>
#include <map>
 
using namespace std;
 
int a[1001];
int b[1001];
map<int, int> mp1;
 
int main()
{
    int t;
    scanf("%d", &t);
 
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
 
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
        scanf("%d", &b[i]);
 
    int sum;
    for (int i = 0; i < n; i++)
    {
        sum = a[i];
        mp1[sum]++;
        for (int j = i + 1; j < n; j++)
        {
            sum += a[j];
            mp1[sum]++;
        }
    }
 
    long long cnt = 0;
    for (int i = 0; i < m; i++)
    {
        sum = b[i];
 
        if (mp1.count(t - sum))
            cnt += mp1[t - sum];
 
        for (int j = i + 1; j < m; j++)
        {
            sum += b[j];
 
            if (mp1.count(t - sum))
                cnt += mp1[t - sum];
        }
    }
 
    printf("%lld", cnt);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>