[프로그래머스] 징검다리

---

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/43236

프로그래머스

---

반응형

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    sort(rocks.begin(), rocks.end());
    rocks.push_back(distance);
    
    int left = 1;
    int right = distance;
    int answer = 0;
    
    while(left <= right){
        int mid = (left + right) / 2;
        int previous = 0;
        int removed = 0;
        
        for (int rock : rocks) {
            int gap = rock - previous;
            if (gap < mid) {
                removed++;
            } else {
                previous = rock;
            }
        }

        if (removed <= n) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return answer;
}

---

📝 풀이

바위 간의 거리를 계산하기 수월하게 오름차순으로 정렬 후 도착지점을 추가해줍니다.

이분 탐색을 위하여 left를 최소 거리 1, right를 최대 거리 distance로 초기화합니다.

현재 mid를 최솟값 거리로 설정하고 모든 바위 간의 거리를 순회하면서 mid보다 작은 거리를 만드는 바위를 제거합니다.

제거된 바위의 수가 n보다 작다면 현재 거리 mid를 최솟값으로 유지할 수 있으므로 left를 증가합니다.

그렇지 않다면 바위 제거가 가능한 거리를 찾기 위해 right를 줄입니다.

최종적으로 거리의 최솟값 중 가장 큰 answer을 return 합니다.