[백준] 17266 - 어두운 굴다리 (C++)

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

굴다리의 모든 길 0~N을 밝히게 가로등을 설치하려고 한다. 가로등을 설치할 개수 M과 각 가로등의 위치 x들은 정해져있다. 가로등의 높이가 H라면 왼쪽으로 H, 오른쪽으로 H만큼 주위를 비춘다.

N-5, M=2, H=2일 때 예시

가로등의 높이가 모두 같고 최소한의 높이로 굴다리의 모든 길 0~N을 밝히고자 할 때, 가로등의 최소 높이를 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ N
• 0 ≤ x ≤ N

 

가로등의 높이를 매개변수로 놓고 이분탐색을 진행해야 한다. 모든 가로등마다 밝힐 수 있는 마지막 위치를 기록하고, 0~N 중 밝힐 수 없는 부분이 생긴다면 l을 늘리고, 다 밝힐 수 있다면 r을 줄인다. 이렇게 가로등 높이의 최솟값을 구해 출력해야 한다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, M, 가로등 위치 정보 입력받기
2. 가로등 높이를 매개변수로 놓고 이분탐색 진행
   1. l을 0으로, r을 n으로 놓기
   2. last 변수에 빛이 마지막으로 닿는 곳의 좌표 저장
   3. 모든 길을 밝힐 수 없다면 l = mid+1로 놓기 / 있다면 r = mid-1로 놓고 ans 값 갱신하기
3. ans 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
using namespace std;

int n,m,arr[100001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i=0; i<m; i++) cin >> arr[i];

    int l=0,r=n,ans=100001;
    while (l<=r) {
        int mid = (l+r)/2,last=0;
        bool flag = true;
        for (int i=0; i<m; i++) {
            if (arr[i]-mid>last) {
                flag = false;
                break;
            } 
            else {
                last = arr[i] + mid;
            }
        }
        if (n-last>0) flag = false;

        if (flag) {
            r = mid-1;
            ans = min(ans,mid);
        }
        else {
            l = mid+1;
        }
    }
    cout << ans;
}