<JUNGOL > 환경부의 나무 심기 프로젝트 #5804

문제 : https://www.jungol.co.kr/problem/5804

무엇을 구하는 문제인가?

N개의 가로수를 심을 수 있는 위치와 C개의 나무가 주어졌을때, 나무 사이의 간격을 최대로하여 나무를 심고싶다. 이때의 나무 사이의 거리의 최댓값을 구하는 문제이다.

​

해결 전략

-나무사이의 최대거리를 이분탐색으로 찾았다.

-나무사이의 최대거리가 k일때, 심을 수 있는 최대 나무의 수를 mid_res로 두고 탐색함.

​

알고리즘

1. N, C, 그리고 N개의 나무를 심을 수 있는 위치를 입력받는다.

2. 나무를 심을 수 있는 위치배열(x)를 sort해준다.

3. low = 1, high = x[n-1] - x[0]으로 한다.

4. low <= high 인동안 반복

-mid = (low + high)/2

-mid_res = 나무사이의 최대거리가 mid일때, 심을 수 있는 최대 나무의 수

-mid_res < c -> high = mid - 1

-아니면 low = mid + 1

5. low - 1출력

​

<소스코드>

 

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, c;
int x[200010];

int pandas(int a)
{
    int i, cnt = 1;
    int last = x[0];
    for (i = 1; i < n; i++) {
        if (last + a > x[i]) continue;
        last = x[i];
        cnt++;
    }
    return cnt;
}

int main()
{
    int i, j;
    scanf("%d %d", &n, &c);
    for (i = 0; i < n; i++) scanf("%d", &x[i]);
    sort(x, x + n);
    int low = 1, high = x[n - 1] - x[0];
    while (low <= high) {
        int mid = (low + high) / 2;
        int mid_res = pandas(mid);
        if (mid_res < c) high = mid - 1;
        else low = mid + 1;
    }
    printf("%d", low - 1);
    return 0;
}

​