도약(이진탐색)

문제 설명

---

개구리가 연못 위에서 놀고 있다. 개구리는 N개의 연 잎 들을 이용해서 이리저리 뛰어 놀고 있다.

개구리가 뛰는 장면을 보던 철수는 개구리가 도약을 하는 경우가 얼마나 있는지 궁금해졌다. 여기서 도약은 아래 조건을 만족하는 경우를 말한다.

1. 개구리가 뛴 거리가 이전에 뛴 거리 이상 뛰지만 그 2배보다 멀리 뛰지는 않는다.
2. 개구리는 오른쪽으로만 뛴다.
3. 개구리는 두 번만 뛴다.
4. 위 세 가지 조건을 만족한다면 어느 곳에서든 시작할 수 있다.

허나, 연 잎 들이 너무 많기 때문에 가능한 횟수가 매우 많아질 것 같다고 생각한 철수는, 개구리가 오른쪽으로 도약하는 경우가 얼마나 되는지 구해달라고 했다. 철수를 위해 프로그램을 짜주자.

입력 설명
첫 번째 줄에는 연 잎의 수 N(3 ≤ N ≤ 1,000)이 주어진다.
두 번째 줄부터 N개의 줄에는 각 연 잎의 좌표가 주어진다. 모든 좌표는 0 이상 108 이하이다.

출력 설명

---

개구리가 오른쪽으로 도약하는 경우의 수를 출력한다.

입력 예시

---

5
3
1
10
7
4

출력 예시

---

4

부가정보

---

개구리가 오른쪽으로 도약하는 경우는 다음 4가지뿐이다.
(1, 3, 7), (1, 4, 7), (4, 7, 10), (1, 4, 10)

#include <stdio.h>
#include <stdlib.h>
#define MAXN ((int)1e3)
int N;//연잎수
int A[MAXN+10];//연잎좌표
 
int cmp(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}
 
int BsLow(int s, int e, int d){//d값 보다 크거나 같은 값 중에 작은 인덱스
    int sol = -1;
    while(s<=e){
        int m=(s+e)/2;
        if (A[m] >= d){
            sol = m;
            e=m-1;
        }
        else{
            s=m+1;
        }
    }
    return sol;
}
int BsUp(int s, int e, int d){//d값 보다 작거나 같은 값 중에 큰 인덱스
    int sol = -1;
    while(s<=e){
        int m=(s+e)/2;
        if (A[m] <= d){
            sol=m;
            s=m+1;
        }
        else{
            e=m-1;
        }
    }
    return sol;
}
int Solve(void){
    int cnt = 0;
    qsort(A, N, sizeof(A[0]), cmp);
    for (int a=0; a<N-2; a++){//첫번째 연 잎 인덱스
        for (int b=a+1; b<N-1; b++){//두번째 연 잎 인덱스
            int first = A[b] - A[a];//첫번째 뛴 거리
            int low = BsLow(0, N-1, A[b]+first);//크거나 같은 값 중에 작은 인덱스
            if (low < 0) break;
            cnt += BsUp(0, N-1, A[b]+2*first) - low + 1;//작거나 같은 값 중에 큰 인덱스
        }
    }
    return cnt;
}
int SolveN3(void){
    int cnt = 0;
    qsort(A, N, sizeof(A[0]), cmp);
    for (int a=0; a<N-2; a++){//첫번째 연 잎 인덱스
        for (int b=a+1; b<N-1; b++){//두번째 연 잎 인덱스
            int first = A[b] - A[a];//첫번째 뛴 거리
            for (int c=b+1; c<N; c++){//세번째 연 잎 인덱스
                int second = A[c] - A[b];//두번째 뛴 거리
                //if ((first <= second) && (second <= 2*first)) cnt++;
                if (first > second) continue;
                if (2*first < second) break;
                cnt++;
            }
        }
    }
    return cnt;
}
void InputData(void){
    scanf("%d", &N);
    for (int i=0; i<N; i++){
        scanf("%d", &A[i]);
    }
}
int main(void){
    int ans = -1;
    InputData();//입력받는부분
 
    //ans = SolveN3();
    ans = Solve();//여기서부터작성
 
    printf("%d\n", ans);//출력하는부분
    return 0;
}