[BOJ] 1477 휴게소 세우기

1.vector로 입력을 받고 순서대로 정렬

2. 구간 길이 구하기 ( 0 ~ L ) 사이의 모든 구간 포함

3. 구간의 길이와 그 구간 내의 구간 개수를 같이 저장해야 한 구간을 여러 번 나눴을 때 거리 계산 가능...?

4. 나눴을 때 소수 값이 나올 수 있다는 점 유의....(이거 때문에 총 8번 시도하게 됐다...)

 

처음 틀렸을 때 여러 케이스를 돌려보니 소수 값이 나온다는 것을 알게 됐다. 그래서 소수 값을 처리하기 위해

while(m--){
        double maxlen = dist.top().first;
        int section = dist.top().second;
        dist.pop();
        dist.push({(maxlen*section) / (section+1) , section+1});
    }

    double ans = dist.top().first;

이 부분에서 모두 double 처리를 해줬다.

그런데도 틀리길래 출력에서 문제가 있는 줄 알았다.

그래서 다시 확인해보니

priority_queue<pair<double, int>> dist;

에서 int, int로 해놓고 double로 안바꿔 놨었다....ㅎ

그래도 또! 틀려서 뭐가 문제인지 봤더니..!

dist에 거리 push할때 for문에서 n-1번 돌려야하는데 n번 돌려서 틀렸었다...ㅎ(멍청이 같은 실수)

마지막으로 고쳐서 냈더니 됐습니다...

반성하겠습니다...

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m ,l; cin >> n >> m >> l;
    vector<int> v(n);
    for(int i = 0; i< n; i++){
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    priority_queue<pair<double, int>> dist;
    dist.push({v[0],1}); //0 ~ 처음 구간
    for(int i = 0; i< n-1; i++){
        dist.push({v[i+1]-v[i], 1});
    }
    dist.push({l - v[n-1], 1}); //마지막 휴게소 ~ 고속도로 마지막

    while(m--){
        double maxlen = dist.top().first;
        int section = dist.top().second;
        dist.pop();
        dist.push({(maxlen*section) / (section+1) , section+1});
    }

    double ans = dist.top().first;
  
    if(int(ans) == ans){
        cout << int(ans) <<"\n";
    }
    else{
        cout << int(ans) + 1 <<"\n";
    }
    return 0;
}