문제출처: https://programmers.co.kr/learn/courses/30/lessons/64062

[1.문제이해]

• 한명이 건널때마다 돌에 적힌 수가 줄어든다.
• 한번에 건널수 있는 거리는 한계가 있다.
• 건널 수 있는 사람의 최대수 정하기

[2.접근방식]

- 시뮬레이션 (정적 탐색)

사람의 수를 정해놓고 최대값을 찾을때까지 변경시키면서 시뮬레이션 하면된다. (이때 탐색중에는 사람의 수 증가는 불가하다.) 단 숫자가 하나씩 증가하는 방식으로 시뮬레이션하면 비효율적이므로 이분탐색을 이용한다.

이때 하늘색 직사각형은 돌이고, 빨간색 선이 정한 사람의 수이다. 이때 모든 하늘색(돌갯수)를 포함하면서 가장큰것을 고르면된다.

- 동적 탐색

시뮬레이션의 경우 최대 log(20억)번의 탐색을 해야한다. 큐나 스택 컨테이너를 이용해서 그때그때 사람의 수를 변경시켜 동적으로 탐색해 한번의 탐색에 끝낼 수 있는 방법은 없을까? 그렇다면 컨테이너에 오래된 돌을 빼며, 최근에 들어온 값을 넣으며 동시에 현재까지 탐색한 돌의 크기중 선택가능한 최대사람수를 저장해야한다. 미제..

[3.알고리즘 선택]

이분탐색

[4.코드]

#include <bits/stdc++.h>
using namespace std;

bool check(vector<int> stones, int k, int mid) {
	int cnt = 0;
	for (int i = 0; i < stones.size(); i++) {
		// 현재 인원 수가 돌의 숫자보다 더 큰 경우가 k번 이상 연속된다면 불가능
		if (stones[i] < mid) {
			cnt++;
			if (cnt >= k) return false;
		}
		else cnt = 0;
	}
	// 돌의 숫자가 0이되는 경우가 k번 이상 연속되지 않는다면 가능
	return true;
}


int solution(vector<int> stones, int k) {
	int answer = 0;

	int right = * max_element(stones.begin(), stones.end());
	int left = 1;

	// 징검다리를 건너는 인원 수를 기준으로 이분탐색
	while (left <= right) {
		int mid = (left + right) / 2;
		if (check(stones, k, mid)) {
			left = mid + 1;
			if (answer < mid) {
				answer = mid;
			}
		}
		else {
			right = mid - 1;
		}
	}

	return answer;
}