본문 바로가기
Problem solving/Programmers

[Programmers] 징검다리 (C++)

by 겸 2023. 7. 4.

문제

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있음

rocks배열 중 n개를 제거했을 때 각 지점 사이 거리의 최솟값 중 가장 큰 값은?

생각할 것

  1. mid : 각 지점 사이의 최대 거리를 의미
  2. 가장 가까운 돌과의 거리를 mid와 비교하고 더 작으면 돌을 빼준다.
  3. 돌을 뺀 갯수가 빼야하는 개수보다 크면 목표 거리를 줄임
  4. 돌을 뺀 갯수가 뺴야하는 개수보다 작으면 돌을 더 놓을 수 있으므로 목표 거리를 늘림

코드

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

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    vector<bool> r(rocks.size(), true);
    int answer = 0;
    int left = 0;
    int right = distance;
    
    sort(rocks.begin(), rocks.end());
    while(left <= right) { 
        int mid = (left + right) / 2;
        int prev = 0;
        int rock_cnt = 0; // 뺀 돌의 개수
        for(int i = 0; i < rocks.size(); i++) {
            if(rocks[i] - prev < mid) rock_cnt++; // 최대 거리보다 작으니 돌을 빼서 거리를 늘려줘야함
            else prev = rocks[i]; // 최대 거리보다 같거나 크므로 돌을 그대로 둠
        }
        if(distance - prev < mid) rock_cnt++; // distance와의 거리 비교
        
        if(rock_cnt > n) { // 돌을 너무 많이 뺐으므로 목표거리를 줄여야 함
            right = mid - 1;
        }
        else { // 돌을 너무 적게 뺐음 목표거리를 늘려서 더 많은 거리 두게 해야함
            answer = max(answer, mid);
            left = mid + 1;
        }
    }
    
    return answer;
}

주의할 것

처음부터 돌 사이의 거리 말고도 끝 distance거리도 생각해야한다!

반응형