문제
한 배열 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을 출력한다.
예제 입력 1
5
4
1 3 1 2
3
1 3 2
예제 출력 1
7
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static ArrayList<Integer> subA, subB;
static int[] A, B;
static int T, N, M;
public static int upperBound(ArrayList<Integer> list, int target) {
int min = 0;
int max = list.size();
while(min < max) {
int mid = (min + max) / 2;
if(list.get(mid) <= target) {
min = mid + 1;
}else {
max = mid;
}
}
return max;
}
public static int lowerBound(ArrayList<Integer> list, int target) {
int min = 0;
int max = list.size();
while(min < max) {
int mid = (min + max) / 2;
if(list.get(mid) >= target) {
max = mid;
}else {
min = mid + 1;
}
}
return max;
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
// 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());
}
// 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());
}
// 각 배열에 대한 부분배열의 합
subA = new ArrayList<>();
for(int i = 0; i < N; i++) {
int sum = A[i];
subA.add(sum);
for(int j = i + 1; j < N; j++) {
sum += A[j];
subA.add(sum);
}
sum = 0;
}
Collections.sort(subA);
subB = new ArrayList<>();
for(int i = 0; i < M; i++) {
int sum = B[i];
subB.add(sum);
for(int j = i + 1; j < M; j++) {
sum += B[j];
subB.add(sum);
}
sum = 0;
}
Collections.sort(subB);
// 이분탐색으로 정답 찾기
long ans = 0;
for(int i = 0; i < subA.size(); i++) {
ans += upperBound(subB, T - subA.get(i)) - lowerBound(subB, T - subA.get(i));
}
System.out.println(ans);
}
}
처음에는 부분배열의 합을 담는 배열 subA, subB를 구하기 위해 DFS를 짰었다.
근데 굳이 그럴 필요 없이 이중 for문을 사용해서 모든 부분배열의 합을 구할 수 있었다.
부분배열의 합을 모두 구하고 이분탐색을 사용해 정답 케이스의 개수를 헤아렸다.
위 방법 말고도 HashMap을 이용해서도 처리가 가능할 듯 하다.
subA, subB에 대한 HashMap에 (숫자, 개수)를 담고 탐색만 하는 것.
귀찮아서 짜보지는 않았다.
subA, subB에 대한 투포인터로 탐색도 가능할 듯.
'알고리즘 문제 > 백준 온라인 저지' 카테고리의 다른 글
[BOJ] 1726 - 로봇 JAVA (0) | 2021.02.20 |
---|---|
[BOJ] 2206 - 벽 부수고 이동하기 JAVA (0) | 2021.02.20 |
[BOJ] 7453 - 합이 0인 네 정수 JAVA (0) | 2021.02.18 |
[BOJ] 1208 - 부분수열의 합 2 JAVA (0) | 2021.02.16 |
[BOJ] 1261 - 알고스팟 JAVA (0) | 2021.02.16 |