문제 링크
7453번 합이 0인 네 정수 : https://www.acmicpc.net/problem/7453
문제 설명 및 해결 아이디어
모든 경우를 다 탐색하면 O(n^4)이기 때문에 시간초과가 난다.
그래서 4개의 배열 A, B, C, D중 A와 B의 가능한 모든 합을 저장한 벡터와 C와 D의 가능한 모든 합을 저장한 벡터를 둔다. 두 벡터의 합이 0이 되는 경우의 수를 찾으면 된다.
두 개의 배열에서 가능한 모든 합을 구하는 것이 O(n^2)이므로 이 문제는 O(n^2longn^2)에 해결이 가능하다.
코드
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 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; #define ll long long int int n, num; vector<int> vt[4]; vector<int> vtAB; vector<int> vtCD; int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) { for (int j = 0; j < 4; ++j) { scanf("%d", &num); vt[j].push_back(num); } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { vtAB.push_back(vt[0][i] + vt[1][j]); vtCD.push_back(vt[2][i] + vt[3][j]); } } sort(vtAB.begin(), vtAB.end()); sort(vtCD.begin(), vtCD.end()); ll ans = 0; ll res, lo, hi; for (int i = 0; i < vtAB.size(); ++i) { res = vtAB[i]; lo = lower_bound(vtCD.begin(), vtCD.end(), -res) - vtCD.begin(); hi = upper_bound(vtCD.begin(), vtCD.end(), -res) - vtCD.begin(); ans += (hi - lo); } printf("%lld\n", ans); return 0; } | cs |
'문제풀기이야기' 카테고리의 다른 글
1208번_부분집합의 합 2_BOJ (0) | 2018.07.18 |
---|---|
2632번_피자판매_BOJ (0) | 2018.07.18 |
12015번_가장 긴 증가하는 부분 수열2 / 가장 긴 증가하는 부분 수열3_BOJ (0) | 2018.07.17 |
1940번_주몽 (0) | 2018.07.17 |
3273번_두 수의 합_BOJ (0) | 2018.07.17 |