[Programmers] 징검다리

https://school.programmers.co.kr/learn/courses/30/lessons/43236

프로그래머스

 

1. Python

def solution(distance, rocks, n):
    ret = 1
    rocks.sort()
    rocks.append(distance)
    left, right = 1, distance
    while left <= right:
        mid = (left + right) // 2
        cnt = 0
        prv = 0
        for cur in rocks:
            if cur - prv < mid:
                cnt += 1
            else:
                prv = cur
        if cnt <= n:
            ret = max(ret, mid)
            left = mid + 1
        else:
            right = mid - 1
    return ret

 

2. C++

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

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int ret = 1;
	sort(rocks.begin(), rocks.end());
	rocks.push_back(distance);
	int left = 1, right = distance;
	while (left <= right) {
		int mid = (left + right) / 2;
		int cnt = 0, prv = 0;
		for (int cur : rocks) {
			if (cur - prv < mid) cnt++;
			else prv = cur;
		}
		if (cnt <= n) {
			ret = max(ret, mid);
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	return ret;
}