프로그래밍 알고리즘

[정올 1357] 합이 0이 되는 4개의 숫자들

꾸준한사람 2023. 1. 3. 07:56
반응형

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=632&sca=99&sfl=wr_hit&stx=1357 

 

JUNGOL

 

www.jungol.co.kr

/*
합이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;
}
반응형