[ALGOSPOT][이분탐색] DARPA

 DARPA

https://www.algospot.com/judge/problem/read/DARPA

<코드>

#include <stdio.h>
 
int main(void){
    int testcase;
    scanf("%d", &testcase);
 
    while (testcase--){
        
        int N, M;
        int camerMI[210];
        double result;
        scanf("%d %d", &N, &M);
 
        for (int i = 0; i < M; i++){
            double temp;
            scanf("%lf", &temp);
            camerMI[i] =temp * 1000;
        }
 
        int left = 0, right = 500000;
        int mid;
    
        
        while (left <= right){
            int count = 1, temp_total = 0;
            mid = (left + right) / 2;
 
            for (int i = 1; i < M; i++){
                temp_total += camerMI[i] - camerMI[i - 1];
 
                if (temp_total >= mid)
                {
                    count++;
                    temp_total = 0;
                }
            }
            
            if (count >= N){
                result = mid;
                left = mid + 1;
                right = right;    
            }
            else{
                left = left;
                right = mid - 1;
            }
    
        }
        result =result / 1000;
        
        printf("%.2lf\n", result);
 
    }
 
    return 0;
}

<문제 푼 요령>

 1. 여기서 중요한 것은 문제에서 답을 찾는게 아니라 예상된 답으로 정답을 찾는것이다.

 2. 정답에 대한 모든 경우수를 알기에는 너무 오래걸리기 때문에 이분탐색으로 찾아서 결정한다.

 3. 입력값이 소수 둘째자리 까지의 실수이기 때문에 계산을 편하기 하기 위해서 1000을 곱해서 정수로 만들어 준다.

 4. 이분탐색의 조건은 우리가 예상으로 한 정답이 받아온 카메라를 최대 몇개까지 설치 할 수 있는지 따져봐서 우리가 구하는 카메라 수보다 작거나 같으면 정답을 값을 올려서 이분탐색하면 아니면 내려서 이분탐색 하면 된다.