Link | 백준 2143번 문제 : 두 배열의 합
이번 문제는 사실 n과 m의 크기가 작기 때문에 brute force로 해결할 수 있다.
이중 반복문을 통해 모든 범위의 합산값을 계산한다.
int[] arr = new int[LEN];
for (int i = 0; i < arr.length; i++) {
int sum = 0;
for (int j = i; j < arr.length; j++) {
sum += arr[j];
// sum = 부분합
}
}
이 때 동일한 합산값에 대해서는 개수를 센다.
Map<Integer, Integer> map = new HashMap<>();
for (int s = 0; s < A.length; s++) {
int sum = 0;
for (int e = s; e < A.length; e++) AS.merge(sum += A[e], 1, Integer::sum);
}
두 배열 A와 B에 대해서 각각의 map을 만든다.
Map<Integer, Integer> AS = new HashMap<>();
for (int s = 0; s < A.length; s++) {
int sum = 0;
for (int e = s; e < A.length; e++) AS.merge(sum += A[e], 1, Integer::sum);
}
Map<Integer, Integer> BS = new HashMap<>();
for (int s = 0; s < B.length; s++) {
int sum = 0;
for (int e = s; e < B.length; e++) BS.merge(sum += B[e], 1, Integer::sum);
}
경우의 수는 다음과 같이 구한다. 이 때 경우의 수는 long이 되어야 한다.
long count = AS.entrySet().stream()
.mapToLong(entry -> (long) BS.getOrDefault(T - entry.getKey(), 0) * entry.getValue())
.sum();
public void solve() throws IOException {
final int T = Integer.parseInt(reader.readLine());
int N = Integer.parseInt(reader.readLine());
int[] A = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int M = Integer.parseInt(reader.readLine());
int[] B = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
Map<Integer, Integer> AS = new HashMap<>();
for (int s = 0; s < A.length; s++) {
int sum = 0;
for (int e = s; e < A.length; e++) AS.merge(sum += A[e], 1, Integer::sum);
}
Map<Integer, Integer> BS = new HashMap<>();
for (int s = 0; s < B.length; s++) {
int sum = 0;
for (int e = s; e < B.length; e++) BS.merge(sum += B[e], 1, Integer::sum);
}
result.append(AS.entrySet().stream()
.mapToLong(entry -> (long) BS.getOrDefault(T - entry.getKey(), 0) * entry.getValue())
.sum());
}