https://www.acmicpc.net/problem/7453
7453번: 합이 0인 네 정수
첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.
www.acmicpc.net
upperbound와 lowerbound를 연습하기 위해 풀었습니다..
이 문제도 위의 문제와 같이 두 그룹으로 나눠서 이분탐색을 통해 값의 조합을 구하는 문제입니다.
먼저 list가 4개씩 주어지는데 크기가 4000이므로 2차원 배열을 이용하여 두 그룹으로 나눠줍니다.
그 다음 이분탐색으로 합이 0이되는 조합의 갯수를 upperbound-lowerbound로 찾아주면 되겠습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int list[][], N;
static long sumlist[][], ans;
static int upperbound(int l, int r, long x) {
while (l < r) {
int m = (l + r) / 2;
if (sumlist[1][m] <= x)
l = m + 1;
else
r = m;
}
return l;
}
static int lowerbound(int l, int r, long x) {
while (l < r) {
int m = (l + r) / 2;
if (sumlist[1][m] < x)
l = m + 1;
else
r = m;
}
return r;
}
static void binarysearch(int l, int r, long x) {
if (l > r)
return;
int m = (l + r) / 2;
if (sumlist[1][m] + x == 0) {
ans += (upperbound(0, N * N, sumlist[1][m]) - lowerbound(0, N * N, sumlist[1][m]));
return;
} else if (sumlist[1][m] + x < 0)
binarysearch(m + 1, r, x);
else
binarysearch(l, m - 1, x);
}
static void func() {
Arrays.sort(sumlist[1]);
for (int i = 0; i < N * N; i++) {
binarysearch(0, N * N - 1, sumlist[0][i]);
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = new int[4][N];
sumlist = new long[2][N * N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
list[0][i] = Integer.parseInt(st.nextToken());
list[1][i] = Integer.parseInt(st.nextToken());
list[2][i] = Integer.parseInt(st.nextToken());
list[3][i] = Integer.parseInt(st.nextToken());
}
for (int i = 0, k = 0; i < N; i++) {
for (int j = 0; j < N; j++, k++) {
sumlist[0][k] = list[0][i] + list[1][j];
sumlist[1][k] = list[2][i] + list[3][j];
}
}
}
public static void main(String[] args) throws Exception {
input();
func();
System.out.println(ans);
}
}
|
cs |
'algorithm > binarysearch' 카테고리의 다른 글
| boj 2295 세 수의 합 (0) | 2022.06.28 |
|---|---|
| boj 2110 공유기 설치 (0) | 2021.04.13 |
| boj 2143 두 배열의 합 (0) | 2021.01.22 |
| boj 2805 나무 자르기 (0) | 2021.01.22 |
| boj 1920 수 찾기 (0) | 2021.01.22 |