백준 13423 Three Dots

<링크>

https://www.acmicpc.net/problem/13423

<소스코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

#include<stdio.h> #include<vector> #include<algorithm> using namespace std; int serch(int); vector<int> v;   int main() {     int T;     scanf("%d", &T);     while (T--)     {         v = vector<int>();         int ans = 0;         int N;         scanf("%d", &N);         for(int i=0;i<N;++i)         {             int tmp;             scanf("%d", &tmp);             v.push_back(tmp);         }         sort(v.begin(), v.end());         for(int i=0;i<N-1;++i)             for (int j = i + 1; j < N; ++j)             {                 int d=v[j] - v[i];                 if (serch(v[j] + d))                     ++ans;             }         printf("%d\n", ans);     } } int serch(int target) {     int l = 0;     int r = v.size() - 1;     while (l <= r)     {         int m = (l + r) / 2;         if (v[m] == target)             return 1;                  if (v[m] > target)             r = m - 1;         else             l = m + 1;     }     return 0; } Colored by Color Scripter

cs

<풀이>

출제의도는 이분탐색인 것 같다. 두 점을 찍고, 나머지 한 점이 있는지 없는지 이분탐색으로 확인한다.

시간은 N^2*(logN)이 걸린다.

다른 풀이 방법도 있는데 

<소스코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

#include<stdio.h> #include<algorithm> using namespace std; int dot[1000]; int main() {     int T;     scanf("%d", &T);     while (T--)     {         int N;         scanf("%d", &N);         for (int i = 0; i < N; ++i)             scanf("%d", dot + i);         sort(dot, dot + N);         int ans = 0;         for (int i = 1; i < N - 1; ++i)         {             int l = 0;             int r = N - 1;             while (l < r)             {                 int ldis = dot[i] - dot[l];                 int rdis = dot[r] - dot[i];                 if (ldis == rdis)                 {                     ++ans;                     ++l;                 }                 else if (ldis < rdis)                     --r;                 else                     ++l;             }         }           printf("%d\n", ans);     } } Colored by Color Scripter

cs

<풀이>

s++ e--를 이용하는 방법이다. 가운데 점을 찍고, 좌측끝과 우측끝에서부터 간격을 비교하며

좌간이 넓으면 좌++ , 우간이 넓으면 우-- 한다.

이렇게 하면 중앙점한번 찍을때마다 모든 노드를 확인하기 때문에 N^2으로 끝낼 수 있다.