7453번: 합이 0인 네 정수
문제 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. 출력 합이 0이 되는 쌍의 개수를 출력한다. 예제 입력 1 복
www.acmicpc.net
이 문제를 접했을 때 마침 STL 컨테이너 set, multiset, map, multimap 에 대해서 공부하고 난 뒤였다.
그래서 빠른 검색속도가 핵심인 multiset을 이용하여 구현해보려고 했었다.
A와 B를 모두 더한 순차열을 저장하고, C와 D를 모두 더한 순차열을 저장하는 두 개의 multiset 객체에
count 멤버함수를 사용하여 C와 D를 더한 객체에 -(A-B) 값(합쳐서 0이 되는 값)이 몇개 존재하는지 확인한 다음 갯수를 카운팅 하는 식으로 코드를 구현했는데 시간초과가 떴다. 연관 컨테이너(set, multiset, map, multimap)는 원소를 검색하는데 로그 시간 복잡도를 보장해준다고 배워서 시간 초과가 안나올줄 알았는데 시간초과가 나와서 당황했다.
구글링하다 접하게된 정보인데 아무래도 위에서 설명하는 특성때문에 시간초과가 난거같다. ㅜㅜ
그래서 vector컨테이너를 사용해서 구현하였다.
분명 multiset과 같이 이진 검색을 이용한 알고리즘인데 시간초과가 안난게 아직 풀리지 않은 의문이다.
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> CD;
long long zeroSum = 0;
void Solution(int here)
{
int lower_iter, upper_iter;
lower_iter = lower_bound(CD.begin(), CD.end(), -here) - CD.begin();
upper_iter = upper_bound(CD.begin(), CD.end(), -here) - CD.begin();
if (lower_iter == upper_iter) return;
zeroSum += upper_iter - lower_iter;
}
int main(void)
{
int col;
int a[4001], b[4001], c[4001], d[4001];
cin >> col;
for(int i=0; i<col; i++)
cin >> a[i] >> b[i] >> c[i] >> d[i];
for(int i=0; i<col; i++)
for (int j = 0; j < col; j++)
CD.push_back(c[i] + d[j]);
sort(CD.begin(), CD.end());
for (int i = 0; i < col; i++)
for (int j = 0; j < col; j++)
Solution(a[i] + b[j]);
cout << zeroSum << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 21day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 6679번: 싱기한 네자리 숫자 (0) | 2020.04.28 |
|---|---|
| 백준 1074번: 게임 (0) | 2020.04.28 |
| 백준 1038번: 감소하는 수 (0) | 2020.04.25 |
| 백준 1051번 : 숫자 정사각형 (0) | 2020.04.24 |
| 백준 3085번: 사탕 게임 (c++) (0) | 2020.04.24 |