[백준/C++] 17266번 : 어두운 굴다리

https://www.acmicpc.net/problem/17266

• 코드

#include<iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdio.h>
#include <queue>
#include <vector>
#include <unordered_map>
#include <set>
#include <map>
#include <cmath>
#include <stack>
#include <deque>
#include <bitset>

using namespace std;

vector <int> stand;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
   
    int n, m;
    cin >> n;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        stand.push_back(x);
   }
    int ans = max(stand[0], n - stand[stand.size() - 1]);
    for (int i = 0; i < m-1; i++) {
        int h = (stand[i + 1] - stand[i]);
        if (h % 2 == 1) {
            h = h / 2 + 1;
            if (ans < h) ans = h;
        }
        else {
            h = h / 2;
            if (ans < h) ans = h;
        }
        
    }
    cout << ans << endl;

 
}

• 문제해설

이분 탐색으로 풀다가 시간초과가 날 것 같고 다른 방법은 도저히 생각이 안나던 찰나에 어쩔수 없이 구글링해서 여러 분들이 올린 블로그를 찾아보다가 한분의 알고리즘을 빌려 겨우 해결했다...

물론 이분탐색으로도 풀 수 있는 방법이 있었겠지만 나의 경우엔 이분탐색의 틀에 갇혀있었다는 것을 깨달았다... '최소 가로등의 높이'면서 모든 공간을 비추는 방법을 찾는 것이기 때문에

"가로등 사이의 간격의 2분의 1, 첫가로등과 다리 시작까지의 거리, 마지막 가로등과 다리 끝까지의 거리중 최댓값을 찾아라"

가 위대하신 한 블로거 분의 해답이었다...ㅎㅎ 코드는 보지 않고(이분 탐색으로 풀지 않으셨다는 것만 확인하고) 이 말에만 망치로 얻어맞은 후 내가 짠 코드이다. 

골드 4까지 올라왔으면서 아이디어가 좀 필요한 문제만 마주치면 실버 4도 쉽게 못풀어버리는 나 어떡하지.....ㅎㅎㅎㅎ ㅠㅠ

아래는 위대한 블로거 분의 링크

https://velog.io/@caaaden/%EB%B0%B1%EC%A4%80-17266-%EC%96%B4%EB%91%90%EC%9A%B4-%EA%B5%B4%EB%8B%A4%EB%A6%AC

백준 17266 어두운 굴다리