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;
}