[c++] 17266번: 어두운 굴다리

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

17266번: 어두운 굴다리

 

문제 요약

굴다리 N개, 설치할 가로등 M개,  각 가로등의 위치 X

가로등의 최소한의 높이로 굴다리 N개를 모두 밝히고자 한다. (모든 가로등은 높이가 동일하다)

가로등의 높이가 H라면 왼쪽으로 H, 오른쪽으로 H만큼 주위를 비춘다.

가로등의 최소 높이는?

 

범위

굴다리의 길이 N (1 ≤ N ≤ 100,000)

가로등의 개수 M (1 ≤ M ≤ N)

설치할 가로등의 위치 x (0 ≤ x ≤ N, 정수)

가로등의 위치 x는 오름차순으로 입력되고 중복되지 않는다.

 

 

---

 

최소 높이 H 일 때, 가로등 M개로 굴다리 N개를 모두 밝힐 수  있는가?

 

가로등 높이의 범위는 0~N이다. 그보다 높은 가로등이 있을 수 있지만 최대 중에 최솟값을 찾아야 하기 때문에 0부터 N까지의 거리를 모두 밝힐 수 있는 가로등의 길이가 H의 최대 값이 된다. last라는 변수를 통해 밝혀진 곳의 다음부터 시작하도록 한다. 시작은 0부터.

 

 

우선, 가로등의 위치가 입력되므로 0부터 입력된 첫번째 가로등(오름차순으로 입력되기 때문에 정렬할 필요 없다)까지 밝아야 하므로 

x[0] - last 가 height 보다 작거나 같아야 한다.

x[0] - last <= height

가로등이 비추는 곳 이후 위치로 last를 업데이트 시켜주고 만약 height 보다 더 크다면 return false로 나간다. 한 곳이라도 밝지 않으면 상빈이가 지나갈 수 없으므로.

 

 

모든 가로등에 대해서 수행이 끝나면 마지막까지 가로등이 비춘 위치가 N(굴다리 개수)보다 크거나 같다면 return true를 해준다.

이 중 가장 작은 값을 출력하면서 끝낸다.

→ 이분 탐색을 진행해서 calc()함수에서 true를 리턴하면 범위 R을 mid-1 시켜줘 더 작은 값을 찾을 수 있도록 하기 때문에 따로 더 작은 ans를 찾기 위해 코드를 추가하지 않아도 된다.

 

//17266번: 어두운 굴다리
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, x[100002];

void input(){
    cin >> n;
    cin >> m;
    for(int i=0; i<m; i++) cin >> x[i];
}

bool calc(int height){
    int last = 0;
    for(int i=0; i<m; i++){
        if(x[i] - last <= height) last = x[i] + height;
        else return false;
    }
    return last >= n;
}

void solution(){
    int L = 0, R = n, ans = 0;
    while(L <= R){
        int mid = (L+R)/2;
        if(calc(mid)){
            ans = mid;
            R = mid - 1;
        }else{
            L = mid + 1;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다. 만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
     언제나 환영합니다. 감사합니다. 화이팅!☃️