[BOJ 백준] 두 배열의 합(2143) C++, Java

링크 : www.acmicpc.net/problem/2143

2143번: 두 배열의 합

 

문제 설명 : 

한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.

예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.

 

T(=5) = A[1] + B[1] + B[2]
      = A[1] + A[2] + B[1]
      = A[2] + B[3]
      = A[2] + A[3] + B[1]
      = A[3] + B[1] + B[2]
      = A[3] + A[4] + B[3]
      = A[4] + B[2] 

 

입력 : 

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.

 

출력 : 

첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다.

 

예제 입력 : 

5
4
1 3 1 2
3
1 3 2

 

예제 출력 : 

7

 

접근법 : 

1) 어떻게 풀 것인가?

두 배열의 연속 부분합의 조합을 모두 확인해, 목표 값 T가 나오는 경우의 수를 확인한다.

 

지난 몇문제를 통해 연속 부분합의 경우 슬라이딩 윈도우, 투 포인터 기법으로 풀면 쉽게 풀린다는 것을 확인했다.

(Ex> 백준 7453 합이 0인 네 정수 https://subbak2.tistory.com/24)

[BOJ 백준] 합이 0인 네 정수(7453) Java

 

완전탐색으로 다 해볼 경우 시간복잡도는 N^2^2로 N이 1,000이기 때문에 시간초과가 발생한다.

 

따라서 이를 logN이나 N으로 줄이는 로직이 필요한데,

백준 7453에서 4개의 배열을 각각 2개의 부분합으로 구해서 처리했듯이,

 

A배열로 구올 수 있는 모든 부분합의 경우를 구하고,

B배열로 구할 수 있는 모든 부분합의 경우를 구해서 Sliding window 투포인터 처리를 하면 된다.

 

① A의 합과 B의 합을 경우의 수를 모두 구해서 각각 오름차순으로 각각 정렬(N^2 시간 소요)

② A 부분합은 최솟값부터, B 부분합은 최댓값부터 투 포인터 출발

③ A 부분합 + B 부분합이 = T일 경우 중복인 합 개수까지 고려해서 정답에 더하기.

④ A 부분합 + B 부분합이 > T인 경우 B부분합 포인터를 낮춰준다. (값을 줄여야 T가 되므로)

⑤ A 부분합 + B 부분합이 < T인 경우 A부분합 포인터를 높혀준다. (값을 늘려야 T가 되므로)

 

자세한 로직은 아래 소스코드 참고.

 

그러면 배열의 합을 구하는 경우의 수 N^2 = 100만.

정렬 하는데 N logN.

마지막 투 포인터를 하는데 N(이 때는 100만)의

시간복잡도가 필요해 문제를 통과하는데는 무리없다.

 

글을 쓰다 든 생각인데

이진탐색(binary search)을 변형해 upper_bound 또는 lower_bound를 통해

답을 찾는 방식도 괜찮을 것 같다. 

(마지막 투 포인터 대신에)

 

2) 시간복잡도

두 배열씩 합을 구하는 시간 1,000*1,000 = 100만, 투 포인터 진행시 100만의 반복문을 진행한다.

여유롭진 않지만 통과하는데 무리는 없다.

ArrayList가 아닌 int[ ] Array 형태 선언시 시간이 절약될 것으로 예상.

(Java 기준 -  1,060ms)

 

3) 공간복잡도

int 100만개 * 2개 배열 + int 1,000개 * 2개 배열 = 약 int 200만개 배열이 든다.

4Bytes (int) * 200만 = 7.6MBytes 로 여유있다. 

 

4) 풀면서 놓쳤던점

특별히 없음.

 

5) 이 문제를 통해 얻어갈 것

투 포인터(two pointer) 활용.

이진탐색을 통해서도 문제풀이가 가능할 것 같다.

각각의 부분합을 만들어 투포인터를 진행하는 비교적 간단한 애드혹(adhoc)적인 요소가 필요하다.

 

Java 코드 : 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.StringTokenizer;

// 두 배열의 합 백준 2143
public class Main {
	
	static int T, N, M;					// T - 목표 숫자, N - A 배열의 개수, M - B 배열의 개수
	static int[] A, B;					// A, B 입력받는 배열
	static int ap, bp;					// a pointer, b pointer
	static long ans;					// ans 정답
	
	static ArrayList<Integer> sumA, sumB;	// A배열의 부분합, B배열의 부분합		
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st; 
		
		// T 입력
		T = Integer.parseInt(br.readLine());
		
		// N, A 배열 입력
		N = Integer.parseInt(br.readLine());
		A = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<N ; i++ ) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		
		// M, B 배열 입력
		M = Integer.parseInt(br.readLine());
		B = new int[M];
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<M ; i++ ) {
			B[i] = Integer.parseInt(st.nextToken());
		}
		
		
		// 1. A로 만들 수 있는 부분합을 만들자
		// 시간복잡도 N^2
		sumA = new ArrayList<Integer>(); 
		for (int i=0; i<N; i++) {
			int tmp = A[i];
			sumA.add(tmp);
			for (int j=i+1; j<N; j++) {
				tmp += A[j];
				sumA.add(tmp);
			}
		}
		
		
		// 2. B로 만들 수 있는 부분합을 만들자
		// M^2
		sumB = new ArrayList<Integer>(); 
		for (int i=0; i<M; i++) {
			int tmp = B[i];
			sumB.add(tmp);
			for (int j=i+1; j<M; j++) {
				tmp += B[j];
				sumB.add(tmp);
			}
		}
		
		
		// 3. A, B로 만들 수 있는 부분합을 정렬 
		sumA.sort(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1-o2;
			}
		});
		sumB.sort(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1-o2;
			}
		});
		
		
		// 4. 투포인터로 T의 개수를 구함  
		int sumASize = sumA.size();
		int sumBSize = sumB.size();
		ap = 0;
		bp = sumBSize - 1;
		ans = 0;
		
		while(ap < sumASize && bp>=0) {
			int aTmp = sumA.get(ap);
			int bTmp = sumB.get(bp);
			int aCnt = 0;
			int bCnt = 0;
			// 4-1. A부분합 + B부분합 = T일 경우
			// 답이 아닐때까지 for문 돌면서 카운트하고 곱을 답에 더해줌
			if(aTmp + bTmp == T) {
				// 낮은 값 포인터 될때까지 상승
				while(ap < sumASize && sumA.get(ap) == aTmp) {
                    ap++;		
                    aCnt++;
                }
				// 높은 값 포인터 될떄까지 감소
                while(bp >= 0 && sumB.get(bp) == bTmp) {
                    bp--;
                    bCnt++;
                }
                ans += (long)aCnt*(long)bCnt;
			}
			// 4-2. 값 초과이므로 값을 깎음 (높은 값 포인터 감소)
			else if(aTmp + bTmp > T) {
                bp--;
            }
			// 4-3. 값 미달이므로 값을 높임 (낮은 값 포인터 증가)
			else { //if(aTmp + bTmp < T) {
                ap++;
            }
		}
		
		// 정답출력
		bw.write(String.valueOf(ans));
		
		bw.flush();
		bw.close();
		br.close();
	}
}

 

C++ 코드 : 

// 두 배열의 합 2143 C++
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <vector>
#include <algorithm>

#define MAX (1000 + 3)

using namespace std;

int T, N, M;			// T - 목표 숫자, N - A배열 크기, M - B배열 크기
int A[MAX];
int B[MAX];
int ap, bp;				// a pointer, b pointer

long long ans;

vector<int> sumA;
vector<int> sumB;

bool ascCompare(const int &a, const int &b) {
	if (a < b) return true;
	return false;
}

void input();


int main() {
	// 입력받는다
	//freopen("input.txt", "r", stdin);
	input();

	// 1. A로 만들 수 있는 부분합을 만들자
	int tmp;
	for (int i = 0; i < N; i++) {
		tmp = A[i];
		sumA.push_back(tmp);
		for (int j = i + 1; j < N; j++) {
			tmp += A[j];
			sumA.push_back(tmp);
		}
	}

	// 2. B로 만들 수 있는 부분합을 만들자
	for (int i = 0; i < M; i++) {
		tmp = B[i];
		sumB.push_back(tmp);
		for (int j = i + 1; j < M; j++) {
			tmp += B[j];
			sumB.push_back(tmp);
		}
	}

	// 3. A, B로 만들 수 있는 부분합을 정렬
	sort(sumA.begin(), sumA.end(), ascCompare);
	sort(sumB.begin(), sumB.end(), ascCompare);

	// 4. 투포인터로 T의 개수를 구함
	int sumASize = sumA.size();
	int sumBSize = sumB.size();
	ap = 0;
	bp = sumBSize - 1;
	ans = 0;

	while (ap < sumASize && bp >= 0) {
		int aTmp = sumA[ap];
		int bTmp = sumB[bp];
		int aCnt = 0;
		int bCnt = 0;
		// 4-1. A부분합 + B부분합 = T일 경우
		// 답이 아닐때까지 for문 돌면서 카운트하고 곱을 답에 더해줌
		if (aTmp + bTmp == T) {
			// 낮은 값 포인터 될때까지 상승
			while (ap < sumASize && sumA[ap] == aTmp) {
				ap++;
				aCnt++;
			}
			// 높은 값 포인터 될떄까지 감소
			while (bp >= 0 && sumB[bp] == bTmp) {
				bp--;
				bCnt++;
			}
			ans += (long long)aCnt * (long long)bCnt;
		}
		// 4-2. 값 초과이므로 값을 깎음 (높은 값 포인터 감소)
		else if (aTmp + bTmp > T) {
			bp--;
		}
		// 4-3. 값 미달이므로 값을 높임 (낮은 값 포인터 증가)
		else { //if(aTmp + bTmp < T) {
			ap++;
		}
	}


	// 정답 출력
	printf("%lld", ans);

	return 0;
}

void input() {
	scanf("%d %d", &T, &N);
	// A 배열 입력받기 
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}

	scanf("%d", &M);
	// B 배열 입력받기 
	for (int i = 0; i < M; i++) {
		scanf("%d", &B[i]);
	}
}
#endif