[BOJ] 2143. 두 배열의 합 - (Java)
Problem
제출일 : 2020-03-17
문제 풀이 시간 : 1H
난이도 : ★★★★
한 배열 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]
Input
첫째 줄에 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을 넘지 않는 정수이다.
Output
첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다.
Example
input
5
4
1 3 1 2
3
1 3 2
output
7
Solution & Inpression
low_bound
와 upper_bound
를 활용하는 문제, 아이디어를 도출해 내는 것이 중요함.
Code
언어 : JAVA
메모리 : 48848 kb
실행 시간 : 948 ms
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main {
static int T, N, M;
static long ans;
static int[] A, B;
static List<Integer> a, b;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
T = sc.nextInt(); // T(-1,000,000,000 ≤ T ≤ 1,000,000,000)
N = sc.nextInt(); // n(1 ≤ n ≤ 1,000)
A = new int[N];
for (int i = 0; i < N; i++) {
A[i] = sc.nextInt(); // 절댓값이 1,000,000을 넘지 않는 정수
}
M = sc.nextInt();// m(1≤m≤1,000)
B = new int[M];
for (int i = 0; i < M; i++) {
B[i] = sc.nextInt(); // 절댓값이 1,000,000을 넘지 않는 정수
}
a = new ArrayList<>();
get(A, a);
b = new ArrayList<>();
get(B, b);
Collections.sort(b);
ans = 0;
for (Integer i : a) {
int val = T - i;
int high = upper_bound(b, val);
int low = lower_bound(b, val);
ans += high - low;
}
System.out.println(ans);
}
private static void get(int[] data, List<Integer> list) {
for (int size = 1; size <= data.length; size++) {
int sum = 0;
for (int i = 0; i < size; i++) {
sum += data[i];
}
for (int i = size; i < data.length; i++) {
list.add(sum);
sum += data[i];
sum -= data[i - size];
}
list.add(sum);
}
}
// lower bound는 찾고자 하는 값 이상이 처음 나타나는 위치
private static int lower_bound(List<Integer> list, int val) {
int start = 0;
int end = list.size();
int mid;
while (start < end) {
mid = (start + end) >> 1;
if (list.get(mid) >= val) {
end = mid;
} else {
start = mid + 1;
}
}
return start;
}
// upper bound는 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치
private static int upper_bound(List<Integer> list, int val) {
int start = 0;
int end = list.size();
int mid;
while (start < end) {
mid = (start + end) >> 1;
if (list.get(mid) <= val) {
start = mid + 1;
} else {
end = mid;
}
}
return start;
}
}
'Problem > BOJ' 카테고리의 다른 글
[BOJ] 1072. 게임 - (Java) (0) | 2020.03.18 |
---|---|
[BOJ] 7453. 합이 0인 네 정수 - (Java) (0) | 2020.03.17 |
[BOJ] 1208. 부분수열의 합 2 - (Java) (0) | 2020.03.16 |
[BOJ] 1806. 부분합 - (Java) (0) | 2020.03.15 |
[BOJ] 2003. 수들의 합 2 - (Java) (2) | 2020.03.15 |