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

링크

https://programmers.co.kr/learn/courses/30/lessons/64062

프로그래머스

풀이

 

디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 구하는 문제이다.

 

먼저 돌의 높이만큼 친구들을 한 번씩 건너게 해서 몇 명의 친구들이 건너갈 수 있는지 찾을 수 있다.

그런데 돌의 높이가 2억까지 되기 때문에 효율성 테스트에서 틀릴 확률이 매우매우 높게 된다.

 

그래서 이분탐색을 이용하여 탐색의 횟수를 줄여야겠다고 생각을 하여 문제를 풀었다.

 

친구들이 계속 돌을 건너다 보면 높은 높이는 친구들의 인원 - 돌의 높이 가 되고

친구들의 인원 - 돌의 높이 == 0 이 될 때가 있다.

 

이때 친구들의 인원- 돌의 높이 == 0 이 연속해서 나타나는 부분이 있을 테고

연속적으로 나타나는 부분이 K 이상이 되면 친구들의 인원을 줄여가고

K 미만이 되면 친구들의 인원을 늘려가도록 했다.

 

그렇게 해서 이분 탐색을 마치게 되면 최대로 건널 수 있는 친구의 인원을 구할 수 있게 된다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 1010
const int INF = 2000000000;

using namespace std;

typedef long long int ll;
int solution(vector<int> stones, int k) {
   int left = 1, right = 200000000, mid;

   while (left <= right) {
      mid = (left + right) / 2;
      vector<int> tmp(stones.begin(),stones.end());
      for (int i = 0; i < stones.size(); i++) {
         tmp[i] -= mid;
      }
      
      int cnt = 0;
      bool check = false;
      for (int i = 0; i < tmp.size(); i++) {
         if (tmp[i] <= 0)
            cnt++;
         else {
            cnt = 0;
         }

         if (cnt >= k) {
            check = true;
            break;
         }
      }

      if (check == true) {
         right = mid - 1;
      }
      else
         left = mid + 1;

   }
   return left;
}