USACO: 도약

문제

개구리가 연못 위에서 놀고 있다. 개구리는 N개의 연 잎 들을 이용해서 이리저리 뛰어 놀고 있다.
 
개구리가 뛰는 장면을 보던 철수는 개구리가 도약을 하는 경우가 얼마나 있는지 궁금해졌다. 여기서 도약은 아래 조건을 만족하는 경우를 말한다.
 
1. 개구리가 뛴 거리가 이전에 뛴 거리 이상 뛰지만 그 2배보다 멀리 뛰지는 않는다.
2. 개구리는 오른쪽으로만 뛴다.
3. 개구리는 두 번만 뛴다.
4. 위 세 가지 조건을 만족한다면 어느 곳에서든 시작할 수 있다.
 
허나, 연 잎 들이 너무 많기 때문에 가능한 횟수가 매우 많아질 것 같다고 생각한 철수는, 개구리가 오른쪽으로 도약하는 경우가 얼마나 되는지 구해달라고 했다. 철수를 위해 프로그램을 짜주자.

 

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

입력
5
3
1
10
7
4

출력
4

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

 

제출은 불가하지만,, 요 문제랑 같은 문제같다 :(

USACO

 

풀이

N이 최대 1000으므로 nC3으로도 문제 해결이 가능하지만, 

lower bound와 upper bound를 구하면 두번째 도약시 시간을 단축할 수 있다.

#include<iostream>
#include<algorithm>
#define MAX 1001
using namespace std;

int N;
int pos[MAX];

void input(){
    cin >> N;
    for(int i=0; i<N; i++) cin >> pos[i];
}

int lowerBound(int low, int high, int data){ // data 이상의 값이 등장하는 첫번째 위치
    int lower = MAX;
    while(low<=high){
        int mid = (low+high)/2;
        if(pos[mid] < data) low = mid+1;
        else{
            high = mid-1;
            lower = min(lower, mid);
        }
    }
    return lower;
}

int upperBound(int low, int high, int data){ // data 이하의 값 중 가장 큰 값의 위치
    int upper = -1;
    while(low<=high){
        int mid = (low+high)/2;
        if(pos[mid] > data) high = mid-1;
        else{
            low = mid+1;
            upper = max(upper, mid);
        }
    }
    return upper;
}

void solve(){
    
    // 1. 정렬
    sort(pos, pos+N);

    // 2. 도약 a -> b -> c
    int ans = 0;
    for(int a=0; a<N-2; a++){
        for(int b=a+1; b<N-1; b++){
            int diff = pos[b] - pos[a];
            int lower = lowerBound(b+1, N-1, pos[b]+diff);
            int upper = upperBound(b+1, N-1, pos[b]+diff*2);
            if(lower!=MAX && upper!=-1) ans += (upper-lower+1);
        }
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solve();
}