[백준,c++] 17266번 - 어두운 굴다리

문제

17266번: 어두운 굴다리

 

코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int N, M;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N>>M;
    vector<int> v(M);
    
    double height = 0;
    for(int i=0; i<M; i++) cin>>v[i];
    
    if(M==1) height = N;
    height = fmax(v.front(), (ceil(N-v.back())));
    for(int i=0; i<M-1; i++){
        height = fmax(height, ceil((v[i+1]-v[i])/2.0));
    }
    
    cout<<(int)height;
}

 

풀이

문제 분류는 binary search로 되어있지만 해당 방법으로 풀이 아이디어를 떠올리지 못해 다른 방법으로 해결했습니다.

1. 맨 처음 가로등은 가로등의 거리만큼 밝혀야 하고, 젤 끝 가로등은 (굴다리의 길이 - 끝 가로등의 길이) 만큼 밝혀야 합니다.
2. ceil은 올림 함수입니다.
3. 그리고 각 가로등 사이는 (가로등 사이 길이/2) 만큼만 밝히면 됩니다.
4. 따라서 1번과 3번중 큰 가로등의 높이를 갱신해가며 굴다리의 길이 N을 모두 비추기 위한 가로등의 최소 높이를 찾습니다