Algorithm) Programmers Level4 징검다리 c++

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

프로그래머스

 

이전 포스팅인 https://kuk6933.tistory.com/148  요 문제를 풀었던 덕에 더 빠르게 감 잡을수 있었습니다

이 문제가 이분탐색 항목에 있었기에 이분탐색을 적용했던거지 쌩으로 나오면 과연 이분탐색을 생각해낼 수 있었을까 하는 생각이 들었습니다 

 

우선 출발점과 도착점도 고려해줘야 하므로 rocks에 넣고 시작했습니다. 그리고 정렬되어 있어야 이분탐색이 가능하므로 정렬해줍니다

 

이제 이분탐색을 진행하는데 가장 중요한것은 어떤 값을 이분탐색의 값으로 할지를 정하는 것입니다.

이 문제에서 요구하는 것은 각 지점 사이의 거리의 최솟값중의 최댓값입니다. (이렇게 쓰니 말이 어려운 듯 한데 문제를 보시면 이해가 됩니다)

그래서 이분 탐색의 값을 각 지점 사이의 거리의 최솟값중의 최댓값으로 잡습니다.

 

코드에서 prev는 이전 돌이 존재하는 위치이고 count는 부순 돌의 수입니다.

while문을 돌 때 마다 돌 사이의 거리를 재면서 최솟값(mid)보다 거리가 작으면 돌을 부숴주고(count++)

거리가 같거나 크면 위치(prev)를 업데이트 해줍니다

 

for문을 다 돈 이후에 count가 n보다 크면 n개의 돌을 부신다는 조건에 부합하지 않으므로hi를 조정한 후 다시 이분탐색 돌아주고

count가 n보다 작거나 같으면 answer에 mid를 넣어주고 low를 조정하고 이분탐색을 다시 진행합니다

 

이분탐색이 끝난 후 answer에 각 지점 사이의 거리의 최솟값중의 최댓값이 담겨있고 이를 return하면 됩니다.

 

주의하실 점은 돌을 n개 부셔야 하는게 아니라 n개 이하를 부셔야 한다고 생각하셔야합니다! 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    rocks.push_back(0);
    rocks.push_back(distance);
    sort(rocks.begin(), rocks.end());
    int lo = 1;
    int hi = distance;
    int mid;
    while(lo <= hi) {
        mid = (lo + hi) / 2;
        int prev = 0;
        int count = 0;
        for(int i=1; i<rocks.size(); i++) {
            if(rocks[i] - prev < mid) {
                count++;
            } else {
                prev = rocks[i];
            }
        }
        if(count > n) {
            hi = mid - 1;
        } else {
            answer = mid;
            lo = mid + 1;
        }
    }
    return answer;
}