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

2019 카카오 개발자 겨울 인턴십

 

문제 링크

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

프로그래머스

---

C++ 풀이

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

bool check(int num, vector<int>& stones, int k) {
	int N = 0;
	for (int i = 0; i < stones.size(); i++) {
		if (stones[i] - num <= 0)
			N++;
		else
			N = 0;

		if (N >= k)
			return false;
	}
	return true;
}

int solution(vector<int> stones, int k) {
	int left = 1;
	int right = 200000001;
	int mid = (left + right) / 2;
	while (left <= right) { //이분탐색으로 가능한 최대 친구 수 찾기
		if (check(mid, stones, k))
			left = mid + 1;
		else
			right = mid - 1;

		mid = (left + right) / 2;
	}
	return left;
}

이분탐색법을 활용하였다.

 

---

참고 사이트 (카카오 해설)

https://tech.kakao.com/2020/04/01/2019-internship-test/

2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설