[백준/C++] 13423번 Three Dots

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

13423번: Three Dots

 

문제분석

직선 위에 서로 다른 N개의 점이 있다.  점 i의 위치는 X_i다. N개의 점들 중 점 a, b, c를 뽑았을 때, 점 a, b사이의 거리와 점 b, c사이의 거리가 같다면 세 점의 간격이 같다고 한다. 이 때 각 테스트 케이스에 대해 N개의 점들 중 간격이 같은 세 점을 뽑은 경우의 수를 모두 구하라.

조건 1. 3≤N≤1,000

조건 2. -100,000,000≤X_i≤100,000,000

 

코드

#include<iostream>
#include<algorithm>

using namespace std;

int binary_search(int start, int end, int s[])
{
    if((s[start]+s[end])%2) return 0; // 두 좌표의 합이 홀수라면 간격을 같게 나누는 정수가 없다.

    int target=(s[start]+s[end])/2;
    int mid=(start+end)/2;

    while(start<=end)
    {
        if(s[mid]==target) return 1;
        else if(s[mid]<target) start=mid+1;
        else end=mid-1;

        mid=(start+end)/2;
    }

    return 0;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int T;
    cin>>T;

    for(int t=0; t<T; t++)
    {
        int N;
        cin>>N;
        
        int s[N], ans=0;

        for(int i=0; i<N; i++)
            cin>>s[i];

        sort(s, s+N); // 이분탐색을 위해 정렬해둔다.

        for(int i=0; i<N; i++) // N개의 점 중에서 두 점 i, j를 고르는 모든 경우의 수
        {
            for(int j=i+2; j<N; j++) // i와 j사이에 적어도 하나의 점이 있도록 j=i+2부터 시작한다.
            {
                ans+=binary_search(i, j, s); // 두 점 사이의 간격을 반으로 나누는 점을 찾는다면 +1
            }
        }
        
        cout<<ans<<'\n';
    }
    
    return 0;
}

 

문제 풀이

처음에는 세 점을 뽑는 모든 경우를 구해 각 경우에 대해 세 점의 간격이 같은지 테스트했다. 하지만 이 때 N=1000이라면 테스트해야 할 경우의 수는 166,167,000가지로 시간 제한 안에 문제를 풀 수 없었다. 더 좋은 방법은 두 점을 뽑고, 이 두 점 사이의 간격을 반으로 나누는 점이 점들의 집합 s안에 있는지 이분탐색으로 찾는 것이다. 풀이 과정은 다음과 같다.

1. 테스트 케이스의 수 T를 입력받는다. 각 테스트 케이스마다 아래의 과정을 반복한다.
2. N개의 점의 좌표를 배열 s에 저장한다.
3. s를 오름차순으로 정렬한다.
4. s에서 두 점을 뽑는다. 이 때 두 점 사이에 적어도 하나의 점이 존재하도록 뽑는다.
5. 이 두 점 사이의 간격을 반으로 나누는 정수가 배열 s 안에 존재하는지 이분탐색으로 찾는다. 이 때 두 점 사이의 간격이 홀수라면 간격을 반으로 나누는 정수 좌표는 없으므로 굳이 탐색하지 않는다. (예를 들어, 두 점의 좌표가 2와 4라면 3이 이 두 점 사이를 반으로 나눌 수 있지만 두 점의 좌표가 2와 5라면 이 두 점 사이를 반으로 나눌 수 있는 정수 좌표는 없다.) 배열 s에서 점을 찾는다면 간격이 같은 세 점을 찾은 것이다.
6. 두 점을 뽑는 모든 경우의 수에 대해 위의 과정을 반복한다.