반응형
http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=632&sca=99&sfl=wr_hit&stx=1357
/*
합이0
hash version : chaining
a + b + c + d = 0 을
a + b = -(c + d) 로 바꾸어 해결, 숫자가 크므로, 전부 하지 않고, 해시하여 상위 24비트만 계산함으로써 100%가 아니라 99.99%로 기대한다.
*/
#include <stdio.h>
typedef unsigned int UI;
typedef long long LL;
const int LM = 4000;
const int SIZE = 1 << 24;
const int MASK = SIZE - 1;
int N, A[LM], B[LM], C[LM], D[LM];
int bcnt;
LL ans;
struct Node {
int key;
LL cnt;
Node*next;
Node*alloc(int nk, Node*p) {
key = nk, cnt = 1, next = p;
return this;
}
}buf[LM*LM + LM], *htab[SIZE];
UI hashF(int key) {
return key & MASK;/// 하위 24bit 사용
}
Node*probing(int key, int hidx) {
Node*p = htab[hidx]; //해시테이블의 해당 hidx 자리에 있는 링크들에서
for (; p; p = p->next) {
if (p->key == key) return p; //똑같은 key를 가진 게 있으면 리턴
}
return NULL;
}
int main() {
//freopen("input.txt", "r", stdin);
int i, j;
scanf("%d", &N);
for (i = 0; i < N; ++i) {
scanf("%d%d%d%d", A + i, B + i, C + i, D + i);
}
// A[] + B[] 프로세스 -> 이렇게 합한 N*N의 값들을 해시에 저장한다.
for (i = 0; i < N; ++i) {
for (j = 0; j < N; ++j) {
int key = A[i] + B[j]; //합해서
int hidx = hashF(key); //해시함수를 돌려서 idx를 뽑아낸다(하위 24비트만 쓴다)
Node*p = probing(key, hidx); //해시테이블 hidx 자리에 동일한 key가 있는지 확인
if (p) p->cnt++; //중복이 존재하면 cnt만 증가
else { //중복이 없으면 새로 할당받음(밀어넣기)
htab[hidx] = buf[bcnt++].alloc(key, htab[hidx]);
}
}
}
// -(C[] + D[]) 프로세스
for (i = 0; i < N; ++i) {
for (j = 0; j < N; ++j) {
int key = -(C[i] + D[j]); //-(C+D) key에서
int hidx = hashF(key);
Node*p = probing(key, hidx); //동일한 key가 나오는 게 있으면,
if (p) ans += p->cnt;//기존의 동일한 key 개수만큼 cnt를 증가한다.(조합수를 구하는 것이므로)
}
}
printf("%lld\n", ans);
return 0;
}
반응형
'프로그래밍 알고리즘' 카테고리의 다른 글
[정올 1411] 두 줄로 타일 깔기 (0) | 2023.01.03 |
---|---|
[정올 1374] 긴 자리 덧셈 뺄셈 (0) | 2023.01.03 |
[정올 1335] 색종이만들기(영역구분) (0) | 2023.01.03 |
[정올 1332] 작명하기 (0) | 2023.01.03 |
[정올 1309] 팩토리얼 (0) | 2023.01.03 |