7453 four Integerโ€™s sum should be zero

์•Œ๊ณ ๋ฆฌ์ฆ˜(์ •๋ ฌ, ์ด๋ถ„ํƒ์ƒ‰)

1. ์•ž ๋‘๊ฐœ ์ •์ˆ˜์˜ ํ•ฉ ๋ฐฐ์—ด, ๋’ค ๋‘๊ฐœ ์ •์ˆ˜์˜ ํ•ฉ ๋ฐฐ์—ด์„ ๋งŒ๋“ฌ.(๋ฐฐ์—ด ๊ฐœ์ˆ˜^2 ๊ฐ€ ํ•ฉ ๋ฐฐ์—ด์˜ ๊ธธ์ด)
2. ๋‘ ๋ฐฐ์—ด์„ ์ •๋ ฌ
3. ์•ž ํ•ฉ ๋ฐฐ์—ด์˜ ์›์†Œ๋ฅผ ํ•˜๋‚˜์”ฉ ๋นผ๋ฉฐ ๊ฒ€์‚ฌ -> ๋’ค ํ•ฉ ๋ฐฐ์—ด์—์„œ, upper_bound - lower_bound ๊ฐ’์ด, ํ˜„์žฌ ์›์†Œ์—์„œ์˜ count ๊ฐ’.
4. count ๋ฅผ ๋”ํ•˜๊ณ  ๋‹ค์Œ ์›์†Œ ๊ฒ€์‚ฌ
5. count ๊ฐ’์„ long long ์œผ๋กœ ์„ ์–ธ

๊ตฌํ˜„

1. lower_bound, upper_bound ๋กœ ๋ช‡๊ฐœ์žˆ๋Š”์ง€ ๊ตฌํ•˜๊ณ , ๊ทธ๊ฑธ count ์— ๋”ํ•˜๋Š” ์‹์œผ๋กœ ๊ตฌํ˜„

๋” ๋น ๋ฅธ ๋ฐฉ๋ฒ•

1. ํ•ฉ ๋ฐฐ์—ด์— ์ค‘๋ณต๋œ ๊ฐ’์ด ๋“ค์–ด๊ฐ€๋Š” ๊ฒŒ ๋ฌธ์ œ.
2. ๊ตฌ์กฐ์ฒด๋ฅผ ์„ ์–ธํ•˜๊ณ , ํ•ฉ๊ณผ, ๊ทธ ํ•ฉ์ด ๋ช‡๋ฒˆ ๋‚˜์™”๋Š”์ง€ ์ €์žฅํ•˜๋Š” ๋ฐฉ๋ฒ•
	-> ๋จผ์ € ํ•ฉ ๋ฐฐ์—ด์„ ๋งŒ๋“ค๊ณ , ๊ฐ™์€ ๊ฐ’์ด ๋‚˜์˜ฌ ๋•Œ๋งˆ๋‹ค, ๊ฐ™์€ ๊ฐ’์˜ ๊ฐ€์žฅ ์•ž์— ์žˆ๋Š” ๊ณณ์— count๋ฅผ ํ•˜๋‚˜์”ฉ ์ฆ๊ฐ€ํ•˜๊ณ  ๋’ค์—์žˆ๋Š” ๊ฐ™์€ ๊ฐ’์€ sum์„ -1๋กœ ๋งŒ๋“ค์–ด ๋ฒ„๋ฆฐ๋‹ค.
	-> ๊ทธ๋ฆฌ๊ณ  ๊ฐ’์ด ๋‹ฌ๋ผ์งˆ๋•Œ๋งˆ๋‹ค count๋ฅผ 1์”ฉ ์ฆ๊ฐ€ํ•˜์—ฌ, ์••์ถ•ํ•œ ๊ธธ์ด๊ฐ€ ๋ช‡์ธ์ง€ ๊ตฌํ•˜๊ธฐ.
	-> ๊ฐ’์„ ์ฐพ์„ ๋•Œ๋Š” ์ด๋ถ„ํƒ์ƒ‰์œผ๋กœ ์ฐพ๋Š”๋‹ค.
3. ์•ž๋ณด๋‹จ ๋А๋ฆฌ์ง€๋งŒ, ์•ž ํ•ฉ๋ฐฐ์—ด์˜ ์›์†Œ๋ฅผ ๊บผ๋‚ผ๋•Œ, ๊ฐ™์€ ์›์†Œ๋ฉด ๋ฐ”๋กœ ํ†ต๊ณผํ•˜๋„๋ก ํ•˜๊ธฐ
	-> ์•ž์—์„œ ์—ฐ์‚ฐํ•œ ๊ฒฐ๊ณผ๋ฅผ ์ด์šฉํ•˜์—ฌ ๋ฐ”๋กœ ํ†ต๊ณผ์‹œํ‚ค์ž.
	-> 130ms ์ค„์ž„

์ฝ”๋“œ

#include <iostream>
#include <algorithm>
#define MAX_ARRAY 4000
 
using namespace std;
 
int intArray[MAX_ARRAY][4];
int firstTwo[MAX_ARRAY*MAX_ARRAY], lastTwo[MAX_ARRAY * MAX_ARRAY];
int numOfArray;
 
void generateSum();
long long getCount();
 
int main() {
	cin >> numOfArray;
	for (int i = 0; i < numOfArray; i++) {
		for (int j = 0; j < 4; j++)
			cin >> intArray[i][j];
	}
 
	generateSum();
	sort(firstTwo, firstTwo + numOfArray*numOfArray);
	sort(lastTwo, lastTwo + numOfArray*numOfArray);
	cout << getCount();
}
 
void generateSum() {
	int index = 0;
	for (int i = 0; i < numOfArray; i++) {
		for (int j = 0; j < numOfArray; j++) {
			firstTwo[index] = intArray[i][0] + intArray[j][1];
			lastTwo[index++] = intArray[i][2] + intArray[j][3];
		}
	}
}
 
long long getCount() {
	long long count = 0;
	int save[2] = { -1,-1 };
	for (int i = 0; i < numOfArray*numOfArray; i++) {
		int temp;
		if (save[0] == firstTwo[i])
			temp = save[1];
		else
			temp = (upper_bound(lastTwo, lastTwo + numOfArray * numOfArray, 0 - firstTwo[i])
				- lower_bound(lastTwo, lastTwo + numOfArray * numOfArray, 0 - firstTwo[i]));
		save[0] = firstTwo[i];
		save[1] = temp;
		count += temp;
	}
	return count;
}