백준 17266 어두운 굴다리

가로등의 위치는 불규칙한 간격을 가지고 놓여 있다. 이 때 모든 굴다리를 비추기 위해서는 가로등 사이의 간격이 가장 큰 것을 찾으면 된다. 왜냐하면 가로등 사이의 간격이 가장 클 때를 기준으로 해 가로등의 높이를 설정하면 나머지 간격들은 무조건 비출 수 있기 때문이다.
두 가로등의 위치를 각각 a, b라고 할 때(a < b), 높이에 비례한만큼 바닥을 비추기 때문에 가장 효율적으로 a와 b사이를 비추기 위해서는 (b - a) / 2만큼의 높이를 가지는 게 최선이다. 따라서 0과 첫 가로등 사이의 거리, 마지막 가로등과 n 사이의 거리를 그리고 나머지 가로등 사이의 거리의 절반들 중 최댓값이 답이다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    int m;
    cin >> m;
    vector<int> pos(m);
    for (auto& e : pos) cin >> e;
    int ans = INT_MIN;
    ans = max(ans, pos[0] - 0);
    ans = max(ans, n - pos[m-1]);
    if (m > 1) {
        for (int i = 0; i < m-1; ++i) {
            int diff = pos[i+1] - pos[i];
            if (diff & 1) {
                diff /= 2;
                diff++;
            } else {
                diff /= 2;
            }
            ans = max(ans, diff);
        }
    }
    cout << ans;
}

위 코드는 내가 처음으로 생각한 코드였는데, 좀 더 간단하게 줄일 방법이 떠올라서 바꿨다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    int m;
    cin >> m;
    vector<int> pos(m);
    for (auto& e : pos) cin >> e;
    int ans = INT_MIN;
    ans = max(ans, pos[0] - 0);
    ans = max(ans, n - pos[m-1]);
    if (m > 1) {
        for (int i = 0; i < m-1; ++i) {
            int diff = pos[i+1] - pos[i];
            diff = (int)ceil(diff / 2.0);
            ans = max(ans, diff);
        }
    }
    cout << ans;
}

두 코드 모두 8ms로 통과해서 조금 더 간단한 코드를 쓰기로 했다!