DARPA (중하, p. 446)

문제#

어떻게 풀었나?#

가장 가까운 두 카메라 간의 간격 정하고, 해당 간격으로 N개의 카메라 설치가 가능한지 평가하여 Binary Search로 풀었다.

주의할 점#

Input으로 들어오는 위치 값이 소수점 아래 둘째자리까지 들어오는데, *100을 하여 int로 저장한 뒤 답을 구하면 문제가 생긴다. 부동소수점 때문에 오차가 생겨서 그렇다. 아래 코드를 실행해보면 28이 출력된다.

printf("%d", (int)(0.29*100));

그래서 *1000을 한 다음 나중에 1000을 나눠야 제대로 AC를 받을 수 있다.

정답 코드#

#include <bits/stdc++.h>
using namespace std;
int N, M;
int pos[201];
bool Judge(int len) {
    int ins = pos[0];
    int cnt=1;
    for(int i=1; i<M; i++) {
        if(pos[i]-ins >= len) {
            ins = pos[i];
            cnt++;
            if(cnt>=N) return true;
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        cin >> N >> M;

        double in;
        for(int i=0; i<M; i++) {
            cin >> in;
            pos[i]=(int)(in*1000.0);
        }
        int lo=0, hi=240000;

        while(lo<=hi) {
            int mid = (lo+hi)/2;
            if(Judge(mid)) lo = mid+1;
            else hi = mid-1;
        }
        printf("%.2lf\n", (double)(lo-1)/1000.0);
    }
    return 0;
}

Comment#

실수 연산은 항상 주의해야 한다는 것을 다시 한번 깨달았다.