[Jungol] 정올 2788 도약

출처: 정올 jungol

O(N3)

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

- 주어지는 Input Data가 오름차순으로 정렬되어 있지 않기 때문에 Sort 해줍니다.

- 개구리는 두 번만 점프하므로 삼중 for문을 이용해서 첫번째 → 두번째 → 세번째 연잎의 거리로 

  도약거리 규칙을 만족하는지 확인하여 처리할 수 있습니다. 

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h> 
#define LM 1000+10
int N;
int leaf[LM], copyLeaf[LM], arr[LM];

void mergeSort(int leaf[], int low, int high) {
    // 0. base condition
    if (low >= high)
        return;

    // 1. divide
    int mid = (low + high) / 2;

    // 2. conquer
    mergeSort(leaf, low, mid);
    mergeSort(leaf, mid + 1, high);

    // 3. merge
    int i = low, j = mid + 1, k = low;
    while (i <= mid && j <= high) {
        if (leaf[i] < leaf[j])
            copyLeaf[k++] = leaf[i++];
        else
            copyLeaf[k++] = leaf[j++];
    }

    while (i <= mid) copyLeaf[k++] = leaf[i++];
    while (j <= high) copyLeaf[k++] = leaf[j++];

    // 4. copy
    for (i = low; i <= high; ++i)
        leaf[i] = copyLeaf[i];
}

 

 

O(N22logN)

이분 탐색을 이용할 수 있습니다. 

첫번째 연잎과 두번째 연잎이 정해지면 세번째로 뛰어야 하는 연잎의 위치를 한정할 수 있습니다.

ex) left[] = { 1 3 4 7 10 } 에서 첫번째 연잎(1), 두번째 연잎(3) 라고 했을 때,

    첫번째 점프 거리 = 3 - 1 = 2 → 다음 연잎까지 점프거리 dist2의 범위 = 2 ≤ dist2 ≤ 2 × 2

    결과적으로 연잎의 위치가 5와 7사이에 있는 것의 개수입니다.

이를 이분탐색을 통해 Lower Bound와 Upper Bound를 찾아 해결할 수 있습니다.

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h> 
#include <stdlib.h>
int N, leaf[1000];
 
int comp(const void* A, const void* B) {
    return *(int*)A - *(int*)B;
}
void input() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%d", leaf + i);
}
 
//d 보다 크거나 같은 값 중에 제일 작은 인덱스
int lower_bound(int start, int end, int d) {
    int mid, sol = -1;
    while (start <= end) {
        mid = (start + end) / 2;
        if (leaf[mid] >= d) {
            sol = mid; end = mid - 1; 
        }
        else start = mid + 1;
    }
    return sol;
}
 
//d 보다 작거나 같은 값 중에 제일 큰 인덱스
int upper_bound(int start, int end, int d) {
    int mid, sol = -1;
    while (start <= end) {
        mid = (start + end) / 2;
        if (leaf[mid] <= d) {
            sol = mid; start = mid + 1; 
        }
        else end = mid - 1;
    }
    return sol;
}
 
int solve() {
    int cnt = 0;
    
    // 오름차순 정렬(연잎 위치)
    qsort(leaf, N, sizeof(leaf[0]), comp);
    
    for (int first = 0; first < N - 2; first++) {
        for (int second = first + 1; second < N - 1; second++) {
            int dist1 = leaf[second] - leaf[first];
            int low = lower_bound(0, N - 1, leaf[second] + dist1);
            if (low < 0) break; // 없는 경우
            int high = upper_bound(0, N - 1, leaf[second] + dist1 * 2);
            cnt += high - low + 1;
        }
    }
    return cnt;
}
int main() {
    input();
    printf("%d\n", solve());
}