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

이분탐색 문제인 걸 알고 계~속 생각해봤지만 진짜 어떤 식으로 접근해야 할지 모르겠어서 찾아봐서 풀었다..

start = 1, end = distance로 두고 mid값을 기준으로 mid보다 거리가 작으면 돌을 제거하는 방식으로 구하는거였다.

예시)
start = 1, end = 25, mid = 13, 2개의 돌 제거
출발 ~ 2 = 2 < 13 -> 2번 돌 제거
출발 ~ 11 = 11 < 13 -> 11번 돌 제거
출발 ~ 14 = 14 > 13 -> 14번 돌 유지
14 ~ 17 = 3 < 13 -> 17번 돌 제거
14 ~ 21 = 7 < 13 -> 21번 돌 제거
14 ~ 25 = 11 < 13 -> 14번 돌 제거

총 5개의 돌 제거-> 거리를 좁혀서 재탐색 (end = mid - 1)

이런식으로 이분 탐색으로 하며 답을 찾아 나간다.

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

using namespace std;

int solution(int distance, vector<int> rocks, int n){
  sort(rocks.begin(),rocks.end());
  int start = 1;
  int end = distance;
  int answer = 0;
  while(start <= end){
    int mid = (start + end) / 2;
    int a = 0;
    int count = 0;
    for(int i=0;i<rocks.size();i++){
      if(rocks[i]-a < mid) count++;
      else{
        a = rocks[i];
      }
    }
    if(distance-a < mid) count++;
    if(count > n){
      end = mid - 1;
    } else{
      start = mid + 1;
      answer = mid;
    }
  }
  return answer;
}
int main(void){
  int distance = 25;
  vector<int> rocks = {2,14,11,21,17};
  int n = 2;
  cout<<solution(distance,rocks,n);

}

이분탐색인걸 알고 풀어도 어떤 식으로 접근해야할 지 감을 못 잡았다.. 공부 좀 해야겠다..